arXiv CS open access

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

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

ESPO: Error-Structured Prompt Optimization via Diagnose, Diversify, and Stabilize Lihao Liu, Peng Tang, Kunwar Yashraj Singh, Shabnam Ghadar AWS Agentic AI

Abstract

arXiv:2609.04197v1 [cs.CL] 3 Sep 2026

Evolutionary prompt optimizers such as GEPA suffer from prompt bloat: each iteration appends rules and caveats, producing prompts up to 3× 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% → 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%).

Introduction

Large language models are increasingly steered through natural-language prompts rather than parameter updates (Brown et al., 2020; Wei et al., 2022). As tasks grow more complex, automated prompt optimizers such as APE (Zhou et al., 2023), OPRO (Yang et al., 2024), MIPROv2 (Opsahl-Ong et al., 2024), and GEPA (Agrawal et al., 2026) have emerged to replace manual trial-and-error with systematic search. Among these, GEPA achieves state-

of-the-art results through an evolutionary loop: it evaluates prompts on training examples, reflects on errors using a strong LLM, proposes mutations, and selects survivors via a Pareto front. A persistent shortcoming of evolutionary prompt optimization is prompt bloat: each iteration tends to append rules and caveats, so prompts grow without bound. In our experiments, GEPA produces prompts up to 3× longer than ESPO’s (1.87× on average) yet less accurate from the same weak start, increasing latency and token cost, and can harm generalization by overfitting to training noise. We trace this to three structural deficiencies in the evolutionary paradigm. (i) Incomplete error observation: GEPA reflects on 3–8 random errors per round; by a coupon-collector argument, observing all systematic failure patterns with 95% probability needs ∼15 rounds, and in the meantime the optimizer accumulates redundant or contradictory rules addressing symptoms rather than root causes. (ii) Limited search diversity: a single mutation operator locks in one bias profile; when it fails on certain error types, it compensates by stacking more rules - inflating length without improving accuracy. (iii) Unreliable selection: point estimation on a small (∼30-example) validation set with ∼10 candidates is a multiple-testing problem, and the optimizer may pick a verbose candidate that ranks first by noise rather than true quality. We propose ESPO (Error-Structured Prompt Optimization), a framework that recasts prompt optimization from evolutionary search to structured statistical estimation. ESPO decomposes optimization into three principled phases. The Diagnose phase analyzes all training errors and clusters them into 3–7 structural patterns, achieving complete error coverage in a single round. The Propose phase generates candidates through K=4 complementary strategies - diagnostic revision, consolidation, ablation, and factual injection - each addressing different error types with different inductive biases.

The Select phase applies bootstrap stability selection (B=20 resamples) to reliably identify the most robust candidate under validation-set noise. ESPO subsumes existing evolutionary methods: setting the number of proposal strategies K=1, bootstrap resamples B=1, and diagnosis batch size m=3 (i.e., only 3 errors observed per reflection round) recovers GEPA, revealing that all three sources of sub-optimality are left unaddressed. Our contributions are threefold. (1) Framework. We introduce ESPO, a three-phase framework (Diagnose–Propose–Select) that unifies prompt optimization as statistical estimation, subsumes existing evolutionary methods as a degenerate case, and is grounded in a generalization bound whose three terms - bias floor, exploration gain, and selection error - each correspond to one phase (§3; full theory in Appendix A). (2) Experiments. On seven public benchmarks starting from an intentionally weak default prompt, ESPO averages 74.67% accuracy versus 70.91% for GEPA (+3.76 pp), while producing prompts 47% shorter (1,004 vs. 1,878 chars) with consistently lower inference latency (§4). (3) Cross-model generalization. Experiments with 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% → 91.40% from default; +56.00 pp over GEPA).

Related Work

Automated prompt optimization. Manual prompt engineering techniques include chainof-thought prompting (Wei et al., 2022) and zero-shot reasoning (Kojima et al., 2022). Automated approaches emerged to reduce human effort: APE (Zhou et al., 2023) uses LLMs to generate and select instructions, OPRO (Yang et al., 2024) optimizes via meta-prompting, and PromptBreeder (Fernando et al., 2024) co-evolves task prompts and mutation operators. Within the DSPy framework (Khattab et al., 2024), COPRO and MIPROv2 (Opsahl-Ong et al., 2024) optimize prompts through Bayesian surrogate models, while GEPA (Agrawal et al., 2026) achieves state-of-the-art results via evolutionary search with Pareto selection and reflective mutation. Recent extensions and theoretical analysis. A fast-growing literature refines the evolutionary loop with richer memory or multi-objective criteria: Re-

flectivePrompt (Zhuravlev et al., 2025) (short/longterm reflection), REMO (Wu and Qu, 2025) (memory-augmented reflection), MemAPO (Liang et al., 2026) (dual-memory for error patterns), MOPrompt (Camara et al., 2025) (multi-objective NSGA-II), Optimas (Wu et al., 2025) (compound AI systems), Grießhaber et al. (Grießhaber et al., 2025) (decomposed evolution), and Promptolution (Zehle et al., 2025) (unified framework). On the theory side, Madras et al. (2025) provide PACBayes generalization bounds showing that perplexity regularization prevents overfitting - a complementary principle to ESPO’s bootstrap-based selection stability. Gradient-based and selection-based methods. A separate line of work tackles prompt optimization through gradient-based or selection-based formulations. TextGrad (Yuksekgonul et al., 2024) uses LLM-generated “textual gradients” to iteratively refine prompts, analogous to backpropagation; while powerful for differentiable-style optimization, it operates on individual examples without structured error clustering, making it susceptible to the same incomplete-observation problem as evolutionary methods. TRIPLE (Shi et al., 2024) frames prompt selection as best-arm identification under a fixed evaluation budget, using bandit algorithms (Successive Halving, Racing) to efficiently allocate evaluations. ESPO’s bootstrap stability selection targets the same selection reliability concern but through resampling rather than sequential elimination, providing complementary guarantees (Lemma 3). Despite this progress, no existing method combines structured error diagnosis to guide candidate generation with selection stability guarantees for small validation sets. Error analysis and systematic failure discovery. Systematic error analysis identifies structured failure modes in models: failure mode discovery (Eyuboglu et al., 2022) extracts coherent error clusters from embeddings, behavioral testing (Ribeiro et al., 2020) probes known failure categories, and slice-based evaluation (Chen et al., 2019) surfaces underperforming data subsets. All of these tools diagnose what the model gets wrong but stop short of feeding the diagnosis back into optimization; ESPO’s Diagnose phase closes this loop by turning clustered error patterns into inputs for the next round of candidate generation. A parallel line of inquiry on contrastive prompting shows that converting a task from generation to selection

mitigates strong model priors at inference time; this generation-vs-selection principle is echoed at the optimization layer by ESPO, which generates K diverse candidates and uses bootstrap resampling to select among them rather than committing to a single generated prompt. Bootstrap, stability selection, and the MDL principle. The bootstrap (Efron and Tibshirani, 1993) and bagging (Breiman, 1996) reduce prediction variance by resampling, and stability selection (Meinshausen and Bühlmann, 2010) uses subsampling for robust variable selection. Our Select phase adapts these principles to candidate prompt selection: a candidate that repeatedly wins across bootstrap resamples is more likely to generalize than one that wins by chance on a single val split. Finally, the MDL principle (Rissanen, 1978; Grünwald, 2007) formalizes Occam’s razor, and recent work (Déletang et al., 2024; Huang et al., 2024) connects LLM compression to benchmark performance, motivating ESPO’s empirical preference for shorter prompts.

ESPO Framework

We present ESPO, which decomposes prompt optimization into three phases: structured error diagnosis (§3.2), multi-strategy candidate generation (§3.3), and bootstrap stability selection (§3.4). 3.1

Problem Formulation

Given a task with training set Dtrain , validation set Dval , and metric M (·), prompt optimization seeks an instruction p∗ that maximizes test performance: p∗ = arg max E(x,y)∼Dtest M (mp (x), y) ,

(1)

p∈Π

where x is the input (e.g., a tweet to classify or a math problem to solve), y is the ground-truth label (e.g., sentiment class or correct answer), mp denotes the LLM module parameterized by instruction p (i.e., the model that concatenates prompt p with input x to produce a prediction), and Π is the space of natural-language prompts. ESPO decomposes this into three phases: Phase 1 (Diagnose): φ = D(Etrain , p) Phase 2 (Propose): P = G(p, φ, S1 , . . . , SK ) Phase 3 (Select):

p∗ = R(P, Dval , B)

(2) (3) (4)

where Etrain is the set of training errors, φ is a structured diagnosis, S1 , . . . , SK are proposal strategies, P is the candidate population, and B is the number of bootstrap resamples.

GEPA as a degenerate case. Let m denote the diagnosis batch size (number of training errors sampled per reflection round). Setting K=1, B=1, m=3 exactly recovers GEPA (Agrawal et al., 2026): (i) diagnosis (m=3 → m=all), GEPA observes an incomplete error snapshot each round; (ii) proposal diversity (K=1 → K=4), GEPA applies a single mutation operator; (iii) selection (B=1 → B=20), GEPA uses point estimation on a small validation set. Each dimension independently tightens one term in the generalization bound (Theorem 1), and the degenerate configuration inherits all three weaknesses simultaneously. 3.2

Phase 1: Structured Error Diagnosis

We collect all training errors under current prompt: Etrain = {(xi , yi , ŷi ) : M (mp (xi ), yi ) = 0, (xi , yi ) ∈ Dtrain }.

(5)

A reflection LLM clusters Etrain into K ∗ structural patterns (K ∗ ∈ [3, 7]): ∗

φ = {(patternk , descriptionk , countk )}K k=1 .

(6)

Each pattern has a description of the failure mode, representative examples, and a count. Clustering is implicit (LLM-based), producing descriptions that feed directly into Phase 2. Key advantage: complete error coverage in one round. GEPA’s m=3 random sample needs ∼15 rounds to observe all patterns with 95% probability by a coupon-collector argument (§3.5), accumulating redundant rules addressing symptoms rather than root causes. 3.3

Phase 2: Multi-Strategy Candidate Generation

Given the diagnosis φ, we generate candidates through K=4 complementary strategies, each conditioned on φ: • S1 (Diagnostic Revision): Revise the prompt to address each error pattern’s root cause using the full diagnosis φ. • S2 (Consolidation): Rewrite the prompt without increasing length - merge redundant rules and tighten language, preventing bloat by construction. • S3 (Ablation): Identify over-triggered rules causing false positives and soften or remove them. • S4 (Factual Injection): Extract domain-specific knowledge from error examples and inject it as factual context.

Population management. Each of the K=4 strategies independently generates 1–2 candidate prompts from the diagnosis φ and the current prompt p0 ; we call this initial generation step the seed phase, which typically produces 4–6 candidates. We then apply two rounds of crosspollination (merging complementary strengths from different candidates) and targeted refinement (addressing residual errors) on the top candidates, capping the population at N =10. Empirically, no single strategy dominates across all datasets (§4.4), confirming the independent-bias assumption key to the exploration gain in our bound (§3.5). 3.4

Phase 3: Bootstrap Stability Selection

Selecting the best candidate from N ≈10 using a small validation set (nval =30) is a multiple-testing problem: a candidate may rank first due to favorable noise rather than true quality. We apply B=20 rounds of bootstrap resampling: p∗ = arg max {b : pi = arg max Acc(pj , Vb )} , pi ∈P

(7)

pj ∈P

where Vb is the b-th bootstrap resample of Dval (sampling nval examples with replacement). In words, we select the candidate that wins the most bootstrap resamples. Ties are broken in favor of shorter prompts. A candidate that consistently ranks first across resamples is robust to data perturbation and more likely to generalize; if p1 > 1/2, the probability of wrong selection decays exponentially with B (Theorem 1). Algorithm 1 summarizes the procedure. ESPO implicitly follows the MDL principle (Rissanen, 1978): clustering compresses n errors into K ∗ ≪ n patterns, ablation removes unused rules, and consolidation rewrites without growth - yielding shorter prompts with no explicit length penalty. 3.5

Theoretical Motivation

Each ESPO phase tightens one term in the test-time generalization gap. Decomposing the gap (§A) into a bias floor, an exploration gain, and a selection error yields: Theorem 1 (ESPO bound; informal). Suppose K strategies produce candidates with Acctest (pk ) = Acc∗ − bk + εk , εk ∼ N (0, σ 2 ), and bootstrap selection uses B resamples. Then the selected prompt p∗ satisfies q 1 E[Acctest (p∗ )] ≥ Acc∗−min bk +σΦ−1(1− K )−O( nlnvalKB ). k

The bound is supported by three lemmas (full statements and proofs in Appendix A): Lemma 1

Algorithm 1 ESPO Optimization Algorithm. Require: Training set Dtrain , validation set Dval , initial prompt p0 , strategies S1 , . . . , SK , bootstrap rounds B Ensure: Optimized prompt p∗ # Phase 1: Diagnose 1: E ← {(xi , yi , ŷi ) : M (mp0 (xi ), yi ) = 0} ▷ collect all errors 2: φ ← C LUSTER E RRORS(E, LLMreflect ) ▷ 3–7 structural patterns # Phase 2: Propose (Seed) 3: P ← {p0 } 4: for k = 1 to K do 5: pk ← Sk (p0 , φ, LLMreflect ) 6: P ← P ∪ {pk } 7: end for # Phase 2: Propose (Iterate) 8: for iter = 1 to 2 do 9: Score all candidates on Dval 10: P ← P ∪ C ROSS P OLLINATE(top(P)) ∪ R EFINE(top(P), φ) 11: Prune P to N =10 by (score, −length) 12: end for # Phase 3: Select (Bootstrap) 13: wins[i] ← 0 for all pi ∈ P 14: for b = 1 to B do 15: Vb ← B OOTSTRAP R ESAMPLE(Dval ) 16: wins[arg maxi Acc(pi , Vb )] += 1 17: end for 18: return p∗ ← P[arg maxi (wins[i], −|pi |)]

(bias reduction via diversity: maxk E[Acc(pk )] ≥ Acc∗ − mink bk ); Lemma 2 (exploration gain via order statistics: drawing K candidates and taking the best yields a σ · Φ−1 (1−1/K) bonus); and Lemma 3 (selection precision via bootstrap: with p1 > 1/2, Pr(wrong selection) ≤ exp(−2B(p1 −1/2)2 )). Two caveats: (i) the constant under O(·) in the selection term is shared between GEPAp and ESPO, so the ∼ 3.8× comparison reflects the ln K/B ratio rather than absolute magnitude; (ii) Lemma 3’s p1 > 1/2 premise holds when best is separated from runners-up by more than validation noise scale, which is the regime our ablation operates in but is not certified per dataset. Why GEPA is suboptimal. Setting K=1, B=1 √ collapses the bound to Acc∗ −b1 −O(1/ nval ): the exploration gain vanishes, the bias term loses the mink improvement, and the selection error stays √ at O(1/ nval ) instead of the ∼3.8×-tighter ESPO rate. A coupon-collector argument (Appendix B) further shows that GEPA’s m=3 random sampling needs ∼15 reflection rounds to observe all error patterns with 95% probability, while full-batch diagnosis (m=n) achieves complete coverage in one

Table 1: Test accuracy (%) and prompt length (characters) on seven benchmarks with Claude Sonnet 4.5 as student. All methods start from the same deliberately weak task prompt. Cell values are the single-run test accuracies from our primary optimization run; ± is std over 3 additional independent optimization seeds. The appendix provides the full 3-seed means and stds. Best accuracy per row in bold. Default

Bootstrap

COPRO

MIPROv2

GEPA

ESPO (Ours)

Dataset

Acc

Len

Acc

Len

Acc

Len

Acc

Len

Acc

Len

Acc

Len

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA

37.60 ±0.20 23.20 ±0.30 32.60 ±0.40 25.80 ±0.30 49.00 ±0.30 48.00 ±0.30 1.61 ±0.19

609 57 110 89 381 187 67

37.80 ±0.20 23.00 ±0.30 36.80 ±0.40 14.40 ±0.30 46.00 ±0.30 48.00 ±0.30 1.53 ±0.12

607 55 84 73 323 159 67

66.60 ±1.80 89.60 ±1.20 36.80 ±1.00 14.60 ±0.90 46.20 ±1.50 48.40 ±1.60 54.30 ±2.00

2,398 871 84 73 323 159 807

74.40 ±1.50 86.60 ±1.40 37.20 ±1.00 14.20 ±0.90 46.40 ±1.50 47.80 ±1.60 1.61 ±0.12

1,673 775 84 73 323 159 1,431

68.60 ±2.20 89.60 ±1.50 96.80 ±0.50 44.00 ±1.80 85.00 ±2.00 53.60 ±2.40 58.80 ±2.30

1,279 1,163 660 2,845 1,948 2,736 2,518

74.78 ±1.18 94.52 ±0.84 96.80 ±0.40 44.80 ±1.40 89.40 ±1.20 62.40 ±1.50 60.00 ±1.60

774 766 660 1,008 1,124 1,934 765

Avg

31.12 ±0.28

214

29.65 ±0.27

195

50.93 ±1.43

674

44.03 ±1.15

645

70.91 ±1.81

1,878

74.67 ±1.16

1,004

round, directly reducing each bk . Empirical alignment. The bound’s three predictions match the ablation in §4.5: Diagnose alone yields +2.0% (bias term), K=1 → 4 adds +2.6% (exploration), and B≥10 picks a more compact, generalizing candidate (selection). Diversity without bootstrap hurts (−1.20%), as predicted: adding K without raising B amplifies selection error.

Experiments

We evaluate ESPO on seven public benchmarks covering classification, multi-hop reasoning, math, and privacy-preserving generation. Our experiments ask: (Q1) Starting from a deliberately weak task prompt, can ESPO recover a prompt that is both more accurate and more compact than baselines? (Q2) Does this hold across student models of different capacity? (Q3) Do the four proposal strategies exhibit genuine diversity? (Q4) Does bootstrap selection outperform point estimation? 4.1

Setup

from an intentionally weak task prompt (e.g. Tweet: a single sentence telling the model to lean “negative”; PUPA: “Refuse to answer”). Each weak prompt is selected as the lowest-accuracy one on a 30-example val probe from a small candidate pool; none is written to favor any optimizer. The goal is to test whether an optimizer can recover a good prompt from a bad one, not whether it can polish an already-good one. Models and Baseline Default student: Claude Sonnet 4.5 (temperature = 0). Cross-model analysis adds Gemma 3 12B, Mistral 14B, Qwen3 32B, Claude Haiku 4.5. Reflection LLM is always Claude Sonnet 4.5 (temperature = 0.7). For baselines: Default (no optimization); Bootstrap (BootstrapFewShot from DSPy (Khattab et al., 2024)); COPRO (Pryzant et al., 2023); MIPROv2 (Opsahl-Ong et al., 2024); GEPA (Agrawal et al., 2026). All methods start from the same weak default prompt. Metrics. Classification accuracy (Tweet, MMLU, HoVer), exact-match with normalization (GSM8K, HotpotQA, ScoNe), semantic F1 (PUPA), prompt length (chars), inference latency (s/example). Testtime inference is deterministic. The 95% binomial CI at p=0.75, n=500 is ±3.8%.

Benchmarks and data splits. We use seven datasets: Tweet (sentiment classification), MMLU (multiple-choice QA), GSM8K (grade school math), HotpotQA (multi-hop QA), ScoNe (natural language inference), HoVer (multi-hop fact verification), and PUPA (privacy-preserving response generation). Tweet, MMLU, and PUPA use direct prediction; the others use chain-of-thought. Each dataset uses 70 training examples for optimization, 30 validation examples, and 500 held-out for test.

Table 1 shows the central finding: when all methods start from the same weak prompt, only reflectionbased optimizers recover a usable prompt, and ESPO recovers the best one on average.

A deliberately weak starting prompt. Prior benchmarks initialize from a hand-crafted, tasktuned prompt that already performs well, leaving little headroom and clustering optimizers within 1– 2 pp of each other. We instead start every method

Non-reflective methods cannot salvage a weak prompt. Bootstrap (29.65%) is slightly worse than the default (31.12%) - few-shot demonstrations atop a misleading instruction just amplify wrong behavior. COPRO (50.93%) and MIPROv2

4.2

Main Results

Default (609c)

GEPA (1,279c)

ESPO (774c)

Classify the tweet by leaning “negative” [deliberately weak seed, 609 chars]

Classify the sentiment... Pay special attention to sarcasm. If the tweet contains “but” consider both clauses. Watch for negation words. Consider emoji sentiment. Double-check ambiguous cases. Note: “not bad” is positive. Beware of rhetorical questions... [truncated, 1,279 chars]

Classify the sentiment of the tweet as positive, negative, or neutral. Sarcasm and rhetorical questions should be interpreted by their intended meaning, not literal words. Treat “not bad” patterns as positive. [774 chars]

37.60%

68.60% (+31.00)

74.78% (+37.18)

Figure 1: Prompt comparison on Tweet, all starting from the same deliberately weak seed (Table 1). GEPA accumulates redundant rules (1.7× longer than ESPO) yet trails ESPO by 6.18 pp. ESPO produces a concise, targeted prompt.

(44.03%) rewrite the instruction and do better, but still trail GEPA/ESPO by 20–30 pp on average and stay near floor on PUPA. These methods require a reasonably good starting prompt to shine, whereas GEPA and ESPO do not. ESPO beats GEPA. ESPO averages 74.67% vs. GEPA’s 70.91% (+3.76 pp; per-cell ±std over 3 seeds in Table 1, and the appendix provides the full 3-seed grid). The paired standard error of the ESPO−GEPA difference √ across the 7 datasets is SE = std({∆i }7i=1 )/ 7 ≈ 1.2 pp, so the Avg gap is ≈3.1× its SE (paired t-test significant at α=0.05). ESPO’s cell value is ≥ GEPA’s on all 7 datasets. Outside-noise wins (>1σ): HoVer (+8.80), Tweet (+6.18), MMLU (+4.92), ScoNe (+4.40); within-1σ ties: GSM8K (tie at ceiling), HotpotQA (+0.80), PUPA (+1.20). We describe HotpotQA and PUPA as on par with GEPA. ESPO’s prompts are shorter. Average length 1,004 vs. 1,878 chars (47% shorter). On HotpotQA, GEPA grows to 2,845 chars while ESPO stays at 1,008 chars with comparable accuracy (44.00% vs. 44.80%). Bootstrap resampling implicitly prefers candidates that retain val accuracy across perturbations - these correlate with concise instructions that do not overfit to training noise. Figure 1 compares prompts produced by Default, GEPA, ESPO. For latency, ESPO also achieves equal or lower perexample latency than GEPA on every task (Table 9); the largest reductions are on chain-of-thought tasks where shorter prompts produce more concise reasoning chains. Constrained GEPA: is gain just length control? To test whether ESPO’s gains come purely from prompt length control, we evaluate a Constrained GEPA variant: standard GEPA augmented with (1) a compact proposer instruction and (2) a length constraint (max_length_ratio = 1.2, preventing bloat beyond 1.2× the seed prompt). This isolates

Table 2: Constrained GEPA vs. standard GEPA and ESPO. Single-seed values (the constrained-GEPA variant was not rerun over 3 seeds); the point-estimate view of Table 1. Length control alone does not improve GEPA. Best accuracy in bold. GEPA

Constrained GEPA

ESPO

Dataset

Acc

Len

Acc

Len

Acc

Len

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA

68.60 89.60 96.80 44.00 85.00 53.60 58.80

1,279 1,163 660 2,845 1,948 2,736 2,518

71.00 89.40 96.60 39.80 86.80 54.18 59.24

740 663 660 751 1,171 2,311 1,904

74.78 94.52 96.80 44.80 89.40 62.40 60.00

774 766 660 1,008 1,124 1,934 765

Avg

70.91

1,878

71.00

1,171

74.67

1,004

whether length control alone can close the gap. Results are in Table 2. Analysis. Constrained GEPA successfully produces shorter prompts (1,171c vs. 1,878c, a 38% reduction), demonstrating that length control alone can reduce prompt bloat. However, this compression fails to improve accuracy: average accuracy moves by only +0.09% (71.00% vs. 70.91%), and on HotpotQA it degrades by −4.20%. The constraint forces GEPA to discard rules indiscriminately - without structured error diagnosis to distinguish essential rules from redundant ones, it cannot determine which rules to keep and which to prune. In contrast, ESPO achieves both shorter prompts and higher accuracy (74.67%, 1,004c) because Phase 1 (structured diagnosis) identifies which error patterns matter, Phase 2 (multi-strategy proposals) generates candidates that are concise by construction (especially S2 : consolidation and S3 : ablation), and Phase 3 (bootstrap selection) favors stable, generalizable candidates - which empirically tend to be shorter. 4.3

Cross-Model Generalization

To test whether ESPO’s gains transfer beyond Claude Sonnet 4.5, we apply every optimizer to

Table 3: Cross-model generalization: test accuracy (%) and prompt length (characters) across four student models. All methods start from the same deliberately weak task prompt; reflection LLM is Claude Sonnet 4.5 throughout. Best accuracy per row in bold. Default

Bootstrap

COPRO

MIPROv2

GEPA

ESPO (Ours)

Model

Dataset

Acc

Len

Acc

Len

Acc

Len

Acc

Len

Acc

Len

Acc

Len

Gemma 3 12B

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA Avg

67.20 70.20 88.18 23.00 78.20 55.00 1.87 54.81

487 522 637 665 1,045 187 67 516

40.80 22.00 70.80 14.80 58.80 48.80 1.67 36.81

607 55 84 73 323 159 67 195

66.20 22.00 70.60 15.20 58.60 48.00 1.00 40.23

625 181 84 73 323 159 267 245

45.20 69.20 70.60 15.60 58.20 50.40 1.65 44.41

1,667 1,760 84 73 323 159 67 590

68.60 69.60 88.18 19.40 77.60 53.00 69.57 63.71

1,279 1,711 660 2,845 1,948 2,076 634 1,593

71.20 70.40 88.40 23.40 79.40 59.60 73.12 66.50

774 148 660 701 1,215 1,045 442 712

Mistral 14B

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA Avg

65.40 70.80 93.39 24.40 74.20 48.40 3.93 54.36

487 522 637 665 1,045 187 67 516

40.20 26.60 38.28 5.44 49.60 49.00 4.37 30.50

607 55 84 73 323 159 67 195

64.40 52.80 41.28 5.42 48.20 48.60 3.69 37.77

1,866 49 84 73 323 159 67 374

63.80 71.40 41.08 5.03 48.60 48.60 36.16 44.95

2,398 1,303 84 73 323 159 3,996 1,191

64.40 71.60 92.80 18.00 76.00 49.40 41.81 59.14

1,279 1,711 660 2,845 1,948 2,170 615 1,604

70.40 71.60 94.59 27.11 78.60 50.00 44.62 62.42

1,019 663 805 1,020 1,171 1,099 229 858

Qwen3 32B

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA Avg

70.60 76.80 15.00 26.20 82.60 49.20 1.93 46.05

487 522 637 665 1,045 187 67 516

43.20 35.80 38.00 7.00 64.80 37.60 1.46 32.55

607 55 84 73 323 159 67 195

54.40 29.60 38.80 6.80 65.40 38.20 72.61 43.69

392 135 84 73 323 159 60 175

55.20 75.20 39.20 7.20 65.20 37.00 53.97 47.57

1,699 1,580 84 73 323 159 505 632

69.00 77.40 35.40 15.40 83.80 58.20 73.18 58.91

1,279 1,711 660 2,845 1,948 2,371 1,124 1,705

71.00 78.20 91.40 27.20 84.20 53.00 74.57 68.51

1,216 771 695 1,108 1,275 346 239 807

Haiku 4.5

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA Avg

51.40 53.60 17.00 13.80 45.80 48.80 6.88 33.90

487 522 637 665 1,045 187 67 516

48.20 53.20 3.60 9.00 45.00 47.00 6.87 30.41

607 55 84 73 323 159 67 195

55.80 53.20 3.40 9.20 45.20 47.40 66.92 40.16

1,910 55 84 73 323 159 443 435

65.20 81.60 3.60 9.00 44.80 47.20 67.72 45.59

1,750 1,426 84 73 323 159 1,949 823

71.00 81.80 90.00 31.20 81.40 48.80 71.69 67.98

1,450 388 367 2,678 2,560 187 606 1,177

73.20 83.00 92.40 33.80 85.20 53.60 69.87 70.15

1,025 107 151 801 725 479 1,097 626

four additional student models - Gemma 3 12B, Mistral 14B, Qwen3 32B, and Claude Haiku 4.5 while keeping Claude Sonnet 4.5 as the reflection LLM. Every method starts from the same weak default prompt and runs its full optimization pipeline from scratch with the new student. Table 3 reports the complete 7-benchmark grid for all six optimizers on each student. Findings. (1) ESPO produces the best average accuracy on every student: Gemma 66.50%, Mistral 62.42%, Qwen3 68.31%, Haiku 70.15% - each strictly above GEPA (63.71%, 59.14%, 59.11%, 67.98%). The largest GEPA → ESPO gap is on Qwen3 (+9.20 pp average). (2) The Qwen3 GSM8K result is striking: Default 15.00% → GEPA 35.40% → ESPO 91.40% (+56.00 pp over GEPA). ESPO’s structured diagnosis cleanly identifies the output-format mismatch silently throttling Qwen3, which GEPA’s rule-accumulation only partially addresses. (3) Bootstrap, COPRO, and MIPROv2 again fail to recover a usable prompt,

averaging 30–48% across students - 15–30 pp behind GEPA/ESPO. (4) ESPO prompts are 30– 60% shorter than GEPA’s across all four students, confirming that the concise-by-construction behavior transfers cleanly across model families. 4.4

Strategy Diversity Analysis

Table 8 (Appendix) reports seed-phase validation accuracy per strategy. No single strategy dominates: diagnostic revision wins on Tweet, consolidation on HotpotQA, ablation ties with diagnostic on MMLU and with consolidation/factual on GSM8K, factual injection wins on HoVer/PUPA. This confirms the independent-bias assumption underlying Theorem 1. 4.5

Ablation Study

We ablate ESPO’s components on Tweet (Table 4; ∆ vs. GEPA). Diagnose = full-batch diagnosis (m=all); Diversity = K=4; Bootstrap = B=20. The ablation reveals a clear progression. Single components: Bootstrap gives the largest individual

Table 4: Ablation on Tweet: ✓ = active, D = Diagnose, K = Diversity (K=4), B = Bootstrap (B=20). Configuration

GEPA baseline Diagnose only Diversity only Bootstrap only D+K D+B K+B ESPO (all)

— ✓ — — ✓ ✓ — ✓

— — ✓ — ✓ — ✓ ✓

— — — ✓ — ✓ ✓ ✓

Acc (%)

∆

68.60 — 70.60 +2.00 67.40 −1.20 72.20 +3.60 70.60 +2.00 70.80 +2.20 67.60 −1.00 74.78 +6.18

Table 5: Hyperparameter sensitivity. Each group varies one parameter while fixing others at ESPO defaults. All differences fall within the 95% binomial CI. Param Value Acc (%)

Len

Sel.

1 2 3 4

72.2 70.0 75.0 74.8

806 922 1,134 774

— — — —

1 10 20 30

73.8 74.0 74.8 74.8

1,214 958 774 774

abl. c.p. c.p. c.p.

3 8 15 all

71.0 69.8 72.6 74.8

1,015 1,148 1,100 774

— — — —

gain (+3.60%), then Diagnose (+2.00%); Diversity alone hurts (−1.20%) - a direct prediction of Theorem 1: adding K without raising B amplifies selection error. Pairs: Diversity+Bootstrap (−1.00%) shows diversity without diagnosis is also detrimental - without structured error coverage, diverse strategies vary randomly rather than complementarily. Diagnose+anything is positive. All three: +6.18%, exceeding the sum of any pair confirming that better candidates require better selection. 4.6

Hyperparameter Sensitivity

Table 5 shows ESPO is robust: accuracy varies ≤5% across settings, within the CI. The default (K=4, B=20, m=all) gives the best accuracy– length trade-off - K=4 is 32% shorter than K=3 at comparable accuracy; B≥10 selects a more stable, compact candidate over the point-estimation pick; full-batch diagnosis yields the highest accuracy and shortest prompt, confirming Proposition 2. Training cost. Costs (Table 10) are dominated by student inference during bootstrap evaluation. ESPO’s reflection tokens are ∼39% of GEPA’s, because structured diagnosis produces more information-dense inputs.

Conclusion

We introduced ESPO (Error-Structured Prompt Optimization), a framework that recasts prompt optimization from evolutionary search to structured statistical estimation. By decomposing optimization into three principled phases - structured error diagnosis, multi-strategy candidate generation, and bootstrap stability selection - ESPO addresses the fundamental weaknesses of the search paradigm: incomplete error observation, limited diversity, and unreliable selection. We showed that existing evolutionary methods like GEPA are a degenerate special case of ESPO, and provided a generalization bound grounding each phase in established results from probability theory and statistics. On seven public benchmarks, ESPO improves average accuracy by +3.76% over the state-of-the-art (74.67% vs. 70.91% for GEPA) and matches or exceeds GEPA on every dataset, while producing prompts 47% shorter (1,004 vs. 1,878 chars) and faster at inference. Cross-model experiments on four additional student models (Gemma 3 12B, Mistral 14B, Qwen3 32B, Claude Haiku 4.5) confirm that the gains transfer broadly, with the largest gap on Qwen3 GSM8K (15.00% → 91.40%).

Limitations

Optimization cost. Although our reflectiontoken usage is ∼39% of GEPA’s (Table 10), bootstrap selection still requires B × N candidateresample evaluations. A full ESPO run with K=4, B=20, N =10 on our 70/30/500 split costs roughly the same as one GEPA run at default settings; practitioners with tighter budgets can lower B or N . Single reflection model and independence. All reflection uses one LLM (Claude Sonnet 4.5, T =0.7); mixing reflection models per strategy is not explored. Theorem 1’s independence assumption is therefore a simplification - candidate distributions across strategies are correlated through the shared LLM - but our empirical exploration gain is consistent with the bound under mild correlation. Coverage of error patterns. Diagnosis relies on the reflection LLM to cluster errors into 3–7 patterns; when patterns are more numerous or subtle (e.g., distributional shifts rather than discrete modes), diagnosis may be incomplete. Scope and reporting. We evaluate on seven public benchmarks across classification, multi-hop

QA, math, NLI, fact verification, and privacypreserving generation; tool use, long context, code, and multi-turn dialogue are out of scope. ESPO’s largest cross-model gains occur where the default prompt is far from the student’s prior (e.g., Qwen3 GSM8K). Main-table cells report the single-run cell with ±std over 3 optimization seeds attached; the appendix gives the full 6×7 3-seed grid. Perdataset gaps within 1σ (HotpotQA +0.80, PUPA +1.20) should be read as on-par with GEPA. Theoretical assumptions. Theorem 1 is stated as an explanatory framework motivating the threephase decomposition rather than as a tight probabilistic guarantee. It relies on three assumptions: (i) proposal strategies are independent (a simplification: all four are conditioned on the same reflection LLM); (ii) validation-set noise is sub-Gaussian (motivated by CLT on n=500 Bernoulli trials); and (iii) the true-best candidate wins each bootstrap resample with probability p1 > 1/2 (holds when the top two candidates are separated by more than one validation std, our empirical regime but not certified per dataset). The appendix quantifies strategy overlap empirically (pairwise Jaccard 0.62, Pearson 0.48 over 500 held-out examples per candidate pair) partial decorrelation, not full independence.

References Lakshya A. Agrawal, Shangyin Tan, Dilara Soylu, Noah Ziems, Rishi Khare, Krista Opsahl-Ong, Arnav Singhvi, Herumb Shandilya, Michael J. Ryan, Meng Jiang, Christopher Potts, Koushik Sen, Alexandros G. Dimakis, Ion Stoica, Dan Klein, Matei Zaharia, and Omar Khattab. 2026. GEPA: Reflective prompt evolution can outperform reinforcement learning. In International Conference on Learning Representations (ICLR). Oral presentation.

Vincent S. Chen, Sen Wu, Zhenzhen Weng, Alexander Ratner, and Christopher Ré. 2019. Slice-based learning: A programming model for residual learning in critical data slices. In Advances in Neural Information Processing Systems (NeurIPS), volume 32. Herbert A. David and Haikady N. Nagaraja. 2003. Order Statistics, 3rd edition. John Wiley & Sons. Grégoire Déletang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. 2024. Language modeling is compression. In International Conference on Learning Representations (ICLR). Bradley Efron and Robert J. Tibshirani. 1993. An Introduction to the Bootstrap. Chapman & Hall/CRC. Sabri Eyuboglu, Maya Varma, Khaled Saab, JeanBenoit Delbrouck, Christopher Lee-Messer, Jared Dunnmon, James Zou, and Christopher Ré. 2022. Domino: Discovering systematic errors with crossmodal embeddings. In International Conference on Learning Representations (ICLR). Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel. 2024. Promptbreeder: Self-referential self-improvement via prompt evolution. In International Conference on Machine Learning (ICML). Daniel Grießhaber, Maximilian Kimmich, Johannes Maucher, and Ngoc Thang Vu. 2025. A toolbox for improving evolutionary prompt search. arXiv preprint arXiv:2511.05120. Peter D. Grünwald. 2007. The Minimum Description Length Principle. MIT Press. Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30.

Leo Breiman. 1996. Bagging predictors. Machine Learning, 24(2):123–140.

Yuzhen Huang, Jinghan Zhang, Zifei Shan, and Junxian He. 2024. Compression represents intelligence linearly. In Conference on Language Modeling (COLM).

Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, and 12 others. 2020. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 1877–1901.

Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. 2024. DSPy: Compiling declarative language model calls into self-improving pipelines. In International Conference on Learning Representations (ICLR).

Sara Camara, Eduardo Luz, Valeria Carvalho, Ivan Meneghini, and Gladston Moreira. 2025. MOPrompt: Multi-objective semantic evolution for prompt optimization. arXiv preprint arXiv:2508.01541.

Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems (NeurIPS), volume 35.

M. R. Leadbetter, Georg Lindgren, and Holger Rootzén. 1983. Extremes and Related Properties of Random Sequences and Processes. Springer-Verlag. Guanbao Liang, Yuanchen Bei, Sheng Zhou, Yuheng Qin, Huan Zhou, Bingxin Jia, Bin Li, and Jiajun Bu. 2026. Generalizable self-evolving memory for automatic prompt optimization. arXiv preprint arXiv:2603.21520. David Madras, Joshua Safyan, and Qiuyi (Richard) Zhang. 2025. Prompts generalize with low data: Non-vacuous generalization bounds for optimizing prompts with more informative priors. arXiv preprint arXiv:2510.08413. EXAIT Workshop, ICML 2025. Nicolai Meinshausen and Peter Bühlmann. 2010. Stability selection. Journal of the Royal Statistical Society: Series B, 72(4):417–473. Krista Opsahl-Ong, Michael J. Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. 2024. Optimizing instructions and demonstrations for multi-stage language model programs. In Empirical Methods in Natural Language Processing (EMNLP). Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. 2023. Automatic prompt optimization with “gradient descent” and beam search. arXiv preprint arXiv:2305.03495. Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. 2020. Beyond accuracy: Behavioral testing of NLP models with CheckList. In Association for Computational Linguistics (ACL). Jorma Rissanen. 1978. Modeling by shortest data description. Automatica, 14(5):465–471. Chengshuai Shi, Kun Yang, Zihan Chen, Jundong Li, Jing Yang, and Cong Shen. 2024. Efficient prompt optimization through the lens of best arm identification. In Advances in Neural Information Processing Systems (NeurIPS). Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V. Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems (NeurIPS), volume 35. Chunlong Wu and Zhibo Qu. 2025. Reflectionenhanced meta-optimization integrating TextGradstyle prompt optimization with memory-driven selfevolution. arXiv preprint arXiv:2508.18749. Shirley Wu, Parth Sarthi, Shiyu Zhao, Aaron Lee, Herumb Shandilya, Adrian Mladenic Grobelnik, Nurendra Choudhary, Eddie Huang, Karthik Subbian, Linjun Zhang, Diyi Yang, James Zou, and Jure Leskovec. 2025. Optimas: Optimizing compound AI systems with globally aligned local rewards. arXiv preprint arXiv:2507.03041.

Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, and Xinyun Chen. 2024. Large language models as optimizers. In International Conference on Learning Representations (ICLR). Mert Yuksekgonul, Federico Bianchi, Joseph Boen, Sheng Liu, Zhi Huang, Carlos Guestrin, and James Zou. 2024. TextGrad: Automatic “differentiation” via text. arXiv preprint arXiv:2406.07496. Tom Zehle, Timo Heiss, Moritz Schlager, Matthias Assenmacher, and Matthias Feurer. 2025. promptolution: A unified, modular framework for prompt optimization. arXiv preprint arXiv:2512.02840. Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. 2023. Large language models are human-level prompt engineers. In International Conference on Learning Representations (ICLR). Viktor N. Zhuravlev, Artur R. Khairullin, Ernest A. Dyagin, Alena N. Sitkina, and Nikita I. Kulin. 2025. ReflectivePrompt: Reflective evolution in autoprompting algorithms. arXiv preprint arXiv:2508.18870.

Appendix A

The expected maximum is at least the (1−1/K)quantile of the best strategy:

Full Proof of Theorem 1

Theorem 1 (Restated). Suppose K independent strategies each produce a candidate with test accuracy Acctest (pk ) = Acc∗ − bk + εk , where bk ≥ 0 and εk ∼ N (0, σ 2 ). A bootstrap selection procedure with B resamples selects the final prompt p∗ . Then: E[Acctest (p∗ )] ≥ Acc∗ − min bk k

1 + σ · Φ−1 1 − K q ln K . −O nval ·B

Proof. We prove the bound by analyzing each of the three terms in the generalization gap decomposition: a bias floor mink bk , an exploration gain from order statistics, and a selection error controlled by bootstrap concentration. A.1

Bias Reduction via Strategy Diversity (Lemma 1) Lemma 1. With K strategies having biases b1 , . . . , bK :

E[max Acc(pk )] ≥ Acc∗ − min bk k k 1 + σ · Φ−1 1 − . K

For the asymptotic case of K identical strategies (same b, same σ), the classical re√ sult E[max of K i.i.d. N (0, 1)] ∼ 2 ln K applies (Leadbetter et al., 1983; David and Nagaraja, 2003). Remark. The bound Φ−1 (1−1/K) is conservative (a lower bound on the expected maximum), making the theorem statement safe. For K=4: Φ−1 (3/4) ≈ 0.674. A.3

Lemma 3: Selection Precision via Bootstrap

Lemma 3. If the true best candidate ranks first in each bootstrap resample with probability p1 > 1/2, then: Pr(wrong selection via plurality vote) ≤ exp −2B(p1 − 21 )2 .

max E[Acctest (pk )] ≥ Acc∗ − min bk . k

Proof. Let Wb = ⊮[true best wins resample b]. Then W1 , . . . , WB are i.i.d. Bernoulli(p 1 ). PluralP ity vote selects the true best if b Wb > B/2. We bound the complementary event:

Proof. Let k ∗ = arg mink bk . Then: max E[Acctest (pk )] ≥ E[Acctest (pk∗ )] k

= Acc∗ − bk∗ ∗

= Acc − min bk .

X b

A.2

≥

Acc∗ −

≥ Pr(Acc(pk∗ ) ≥ t) t − Acc∗ + bk∗ . =1−Φ σ

Setting this probability to 1/K: t − Acc∗ + bk∗ 1 1−Φ = σ K =⇒

t = Acc∗ − bk∗ 1 . + σ · Φ−1 1 − K

= Pr

Wb − Bp1

(8)

By Hoeffding’s inequality (Hoeffding, 1963), for t = p1 − 1/2 > 0:

Proof. Let k ∗ = arg mink bk . Since maxk Acc(pk ) ≥ Acc(pk∗ ) = Acc∗ − bk∗ + εk∗ , for any threshold t: Pr(maxAcc(pk ) ≥ t)

1 . ≤ −B p1 − 2

Lemma 2: Exploration Gain via Order Statistics

Lemma 2. E[maxk Acctest (pk )] mink bk + σ · Φ−1 (1 − 1/K).

B Wb ≤ 2

! Pr

Wb − Bp1 ≤ −Bt

≤ exp(−2Bt2 ).

Therefore Pr(wrong selection) ≤ exp(−2B(p1 − 1/2)2 ). Remark. The assumption p1 > 1/2 requires that the true best candidate wins more often than any other single candidate. This is plausible when the accuracy gap between the best and second-best candidates is non-trivial relative to the noise level. A.4

Combining the Lemmas

By Lemma 2, the population contains a candidate with expected accuracy at least Acc∗ −

mink bk + σ · Φ−1 (1−1/K). By Lemma 3, bootstrap selection identifies this candidate with probability at least 1 − exp(−2B(p1 − 1/2)2 ). The selection error p translates to an accuracy loss of at most O( ln K/(nval · B)): the gap between the best and selected candidate on the test set is bounded by the estimation error on the validation √ set (O(1/ nval )), divided by √ the confidence improvement from B resamples ( B), with a log K correction for multiple testing. For GEPA (K=1, B=1): the exploration gain σ · Φ−1 (1−1/K) vanishes (Φ−1 (0) = −∞, but with K=1 there is no maximum to take), and the √ selection error is O(1/ nval ). Table 6: Term-by-term comparison of the generalization bound for GEPA (degenerate case, K=1, B=1) and ESPO (default K=4, B=20). Term

GEPA (K=1, ESPO (K=4, B=20) B=1)

Bias

Explor. Select.

Improvement

mink bk ≤ b1

0 (no bonus) √ O(1/ nval )

Multiple strategies σ·Φ p (3/4) ≈ 0.67σ Order statistics O( ln 4/(nval · 20)) ∼3.8× tighter −1

Supporting Analysis: Error Pattern Coverage

Proposition 2 (Coupon collector bound). Let n training errors be distributed across K ∗ patterns, with pattern k containing nk errors (mink nk ≥ 1). An optimizer samples m errors uniformly per round. Then T = ⌈n · ln(K ∗ /δ)/(m · mink nk )⌉ rounds are sufficient to observe all K ∗ patterns with probability ≥ 1 − δ. Proof. Let pk = nk /n be the probability of sampling an error from pattern k in a single draw. In T rounds of m samples each, the probability that pattern k is never sampled is: Pr(miss k) = (1 − pk )mT ≤ exp(−pk · mT ).

By union bound: Pr(any pattern missed) X ≤ exp(−pk · mT ) k

≤ K ∗ · exp(− min pk · mT ). k

Setting K ∗ ·exp(− min

k pk ·mT ) ≤ δ and solving:

mT · min pk ≥ ln(K ∗ /δ) k

=⇒

T ≥

n · ln(K ∗ /δ) . m · mink nk

Practical implication. For typical values (K ∗ =5, m=3, n=20, mink nk =2), this gives T ≥ 15. GEPA needs ∼15 reflection rounds to observe all error patterns with 95% probability. Full-batch diagnosis (m=n) achieves complete coverage in T =1, directly reducing each strategy’s bias bk in Theorem 1.

Implementation Details

C.1

Error Clustering Prompt

The reflection LLM receives all error examples and is asked to identify 3–7 recurring failure patterns. For each pattern, it provides: (1) a short descriptive name, (2) the root cause, (3) which error indices belong to it, and (4) a suggested fix for the instruction. The output is a structured list used directly in Phase 2. Concrete example (Tweet dataset). Given 16 training errors on sentiment classification, Phase 1 produces the following diagnosis: • Pattern 1: Sports Commentary → Neutral (4 errors, 25%). Factual event reporting (scores, records) misclassified as positive due to achievement words like “wins” and “legend.” Root cause: instruction conflates objective reporting with subjective sentiment. Fix: “Factual reporting of events/stats is neutral regardless of achievement words.” • Pattern 2: Rankings/Lists → Positive (4 errors, 25%). Implicit positive sentiment in rankings (“top 5 teams,” “earned a spot”) misclassified as neutral. Root cause: rankings inherently carry positive evaluation. Fix: “Rankings and ‘top’ lists express positive sentiment even when stated factually.” • Pattern 3: Sarcasm/Irony (3 errors, 19%). Sarcastic praise misclassified as neutral. Root cause: vague instruction “account for sarcasm” does not specify the sentiment mapping. Fix: “Sarcasm expressing criticism = negative; ironic praise criticizing a subject is negative.” • Pattern 4: Humorous Positive (3 errors, 19%). Playful complaints with joy indicators (“LOL,” “!!”) misclassified as negative. Fix: “Playful complaints with humor/joy indicators signal positive.” • Pattern 5: Entertainment Commentary (2 errors, 12%). Quality statements about music/shows without personal emotion misclassified as positive. Fix: “Content quality commentary without personal emotion is neutral.”

This structured output replaces GEPA’s unstructured reflection on 3 random errors, enabling each proposal strategy in Phase 2 to address root causes rather than symptoms. C.2

Four Proposal Strategy Templates

Each strategy receives the current prompt, the structured diagnosis φ, and strategy-specific instructions: • Diagnostic Revision (S1 ): “Revise the instruction to address each error pattern. Focus on root causes, not symptoms.” • Consolidation (S2 ): “Rewrite the instruction to be more concise without losing information. Merge redundant rules and tighten language. The result must not be longer than the original.” • Ablation (S3 ): “Identify rules that may be overtriggered, causing false positives. Soften or remove them.” • Factual Injection (S4 ): “Extract domainspecific knowledge from the error examples and add it to the instruction as factual context.” C.3

Bootstrap Selection

We draw B=20 bootstrap resamples of the validation set (sampling nval examples with replacement). For each resample, we evaluate all candidates and record the winner. The final selection is the candidate with the most wins, with ties broken by prompt length (shorter preferred). C.4

Hyperparameter Settings and Justification

Table 7: ESPO hyperparameter settings used for all experiments. Parameter

Value

Description

K N B Iters. Stud. temp Refl. temp ntrain nval

4 10 20 2 0.0 0.7 70 30

Number of proposal strategies Max candidates in population Bootstrap resamples Refinement iters after seed Deterministic inference Diverse generation Training examples Validation examples

Justification. K=4 corresponds to four qualitatively distinct error-fixing strategies (diagnostic, consolidation, ablation, factual); adding more strategies (e.g., K=5, 6) would require inventing additional distinct inductive biases without clear motivation. B=20 is grounded in Lemma 3: for p1 =0.7 (true best wins 70% of resamples),

Pr(wrong selection) ≤ exp(−2·20·0.04) = 0.20; increasing to B=30 yields only marginal improvement (0.09). N =10 balances population diversity against computational cost: each candidate requires nval =30 evaluations per bootstrap resample. These hyperparameters were set once before experimentation and not tuned per dataset. C.5

Hyperparameter Sensitivity Analysis (Extended)

Table 5 in the main text presents the sensitivity analysis for K, B, and m. Here we provide additional detail. B sensitivity (extended). The main table omits B=5 for compactness. The full results are: B=1: 73.80% (ablation, 1,214c), B=5: 74.00% (ablation, 1,214c), B=10: 74.00% (cross-pollination, 958c), B=20: 74.80% (cross-pollination, 774c), B=30: 74.80% (cross-pollination, 774c). With B ≤ 5, bootstrap selects the ablation candidate (higher point estimate on validation, longer prompt); with B ≥ 10, it consistently selects the cross-pollination candidate (more robust, shorter prompt, and higher test accuracy), illustrating bootstrap’s ability to identify the truly best candidate by averaging over data perturbations. m sensitivity and error coverage. The diagnosis batch size m controls what fraction of training errors are analyzed. Using the Coupon Collector bound (Proposition 2), m=3 covers ∼19% of error patterns per round, m=8 covers ∼50%, m=15 covers ∼94%, and m=all covers 100%. Full-batch diagnosis (m=all) achieves the highest accuracy (74.78%) with the shortest prompt (774c). Partial sampling produces 31–48% longer prompts (1,015–1,148c) at lower accuracy (69.8–72.6%), as incomplete error observation generates prompts that accumulate redundant rules addressing symptoms rather than root causes.

Additional Experimental Results

D.1

Strategy Diversity

Table 8 reports the seed-phase validation accuracy of each proposal strategy across the seven benchmarks. No single strategy dominates: diagnostic revision wins on Tweet, consolidation on HotpotQA, ablation ties with diagnostic on MMLU and with consolidation/factual on GSM8K, and factual injection wins on HoVer and PUPA. This empirically

Table 8: Seed-phase validation accuracy (%) per strategy (nval =30). No single strategy dominates, confirming the independent-bias assumption. Dataset

Diagnosis Consolid Ablation Factual Inj. Winner 80.00 83.33 93.33 50.00 80.00 50.00 63.65

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA

73.33 80.00 96.67 53.33 80.00 66.67 63.06

73.33 83.33 96.67 50.00 80.00 60.00 62.05

76.67 76.67 96.67 50.00 80.00 70.00 65.84

Diag. D/A C/A/F Cons. Tie Fact. Fact.

over GEPA) is the largest single-cell improvement we observe; the structured diagnosis identifies the output-format mismatch silently throttling Qwen3 in one round, while GEPA’s rule-accumulation only partially addresses it across many. ESPO prompts average 30–60% shorter than GEPA across all four students, mirroring the same-student finding. D.3

Table 9: Inference latency (seconds per example). Lower is better. Mode: P = predict, CoT = chain-ofthought. Dataset

Def.

Boots. COPRO MIPROv2 GEPA ESPO Mode

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA

1.97s 2.24s 1.16s 2.10s 5.02s 5.09s 5.58s 5.69s 6.67s 6.89s 7.11s 17.64s 9.66s 8.91s

2.13s 2.04s 4.92s 5.67s 7.10s 7.72s 9.41s

2.20s 2.26s 5.00s 5.70s 6.97s 7.89s 8.59s

1.93s 1.16s 5.02s 5.67s 7.23s 9.85s 8.81s

1.93s 1.15s 4.96s 5.35s 6.59s 8.38s 8.18s

P P CoT CoT CoT CoT P

supports the independent-bias assumption underlying the exploration-gain term in Theorem 1. D.2

Inference Latency and Training Cost

Table 9 reports per-example inference latency at test time, and Table 10 reports the optimizationtime cost in tokens. ESPO matches or improves GEPA’s latency on every benchmark, with the largest reductions on chain-of-thought tasks where shorter prompts induce more concise reasoning chains. Reflection token usage during optimization is ∼39% of GEPA’s because structured diagnosis produces information-dense inputs. Table 10: Optimization cost per dataset for ESPO (Claude Sonnet 4.5 pricing: $3/M input + $15/M output). Wall-clock times are measured after parallelizing candidate evaluation and strategy proposal. Dataset

Total Tokens

Cost

Wall Clock

Reflect Tokens

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA

∼752K ∼887K ∼3.0M ∼3.0M ∼3.8M ∼1.6M ∼3.4M

$9.99 $10.85 $21.58 $20.80 $25.66 $14.90 $23.20

10m 19m 18m 28m 31m 45m 2h 13m

∼36K ∼38K ∼46K ∼46K ∼33K ∼40K ∼42K

Additional notes. The cross-model gains in §4.3 hold dataset-by-dataset, not just on average: on Qwen3, ESPO is the unique winner on 6/7 datasets (HoVer is the only loss); on Haiku, ESPO wins 6/7 (PUPA is the only loss). The Qwen3 GSM8K result (Default 15.00% → ESPO 91.40%, +56.00 pp

Per-Seed Variance Grid

Table 1 in the main paper reports single-run cell values with ±std over 3 additional seeds attached; Table 11 below gives the full 3-seed grid with each cell’s actual 3-seed mean and std. The 3seed ESPO−GEPA Avg gap is 3.81 pp, close to Table 1’s 3.76 pp headline and larger than either method’s Avg std (1.16 / 1.81), placing the gap outside the noise band. The per-dataset gaps on HotpotQA (+0.79 under 3-seed means, +0.80 singlerun) and PUPA (+1.29 / +1.20) fall within one std and are reported as ties. ESPO’s std is systematically smaller than GEPA’s (Avg 1.16 vs. 1.81), consistent with the bootstrap-stability prediction (Lemma 3). D.4

Strong-Initialization Comparison

The main-paper experiments (§4) intentionally start from a weak seed to test recovery. We chose a minimal unified seed because several baselines (COPRO, MIPROv2) cannot build a prompt from scratch—they only rewrite/augment an existing instruction, so a shared starting point is required for a fair comparison. To probe whether ESPO’s gains depend on the seed being weak, we rerun every method on every dataset with a strong task-tuned seed—one that covers task definition, output format, and 1–2 known-pitfall rules (representative of a competent practitioner’s draft after briefly studying the task). Under a strong seed (Table 12), ESPO averages 4.79 pp above GEPA—a wider lead than the 3.76 pp under the weak seed. Under strong initialization, GEPA’s mini-batch reflection keeps appending marginal rules to an already-good prompt (length grows, accuracy stagnates), while ESPO’s full-error diagnosis targets the small remaining structural gap, and Diversify + Select suppress appended noise. This confirms ESPO is a general prompt optimizer, not limited to repairing weak prompts.

Table 11: Per-seed variance: test accuracy (%; mean ± std over 3 independent optimization seeds) on all seven benchmarks with Claude Sonnet 4.5 as student. Best per row in bold. This is the full grid that Table 1 in the main paper condenses. Dataset

Default

Bootstrap

COPRO

MIPROv2

GEPA

ESPO (Ours)

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA

37.57 ± 0.20 23.05 ± 0.30 32.51 ± 0.40 25.60 ± 0.30 48.95 ± 0.30 47.88 ± 0.30 1.58 ± 0.19

37.91 ± 0.20 22.99 ± 0.30 36.89 ± 0.40 14.43 ± 0.30 46.12 ± 0.30 48.02 ± 0.30 1.61 ± 0.12

66.55 ± 1.80 89.34 ± 1.20 36.68 ± 1.00 14.33 ± 0.90 45.99 ± 1.50 48.15 ± 1.60 54.21 ± 2.00

74.62 ± 1.50 86.65 ± 1.40 37.37 ± 1.00 14.23 ± 0.90 46.58 ± 1.50 47.81 ± 1.60 1.72 ± 0.12

68.72 ± 2.20 89.22 ± 1.50 96.57 ± 0.50 43.98 ± 1.80 84.52 ± 2.00 53.60 ± 2.40 58.57 ± 2.30

74.79 ± 1.18 94.28 ± 0.84 96.65 ± 0.40 44.77 ± 1.40 89.10 ± 1.20 62.40 ± 1.50 59.86 ± 1.60

Avg

31.02 ± 0.28

29.71 ± 0.27

50.75 ± 1.43

44.14 ± 1.15

70.74 ± 1.81

74.55 ± 1.16

Table 12: Strong-initialization comparison: test accuracy (%) when all methods start from a task-tuned instruction (task definition, output format, and 1–2 known-pitfall rules). Same 7 benchmarks, same student (Claude Sonnet 4.5), same reflection LLM as Table 1; only the seed prompt changes. Best per row in bold. Dataset

Default

Bootstrap

COPRO

MIPROv2

GEPA

ESPO (Ours)

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA

65.20 82.40 88.60 32.60 66.40 54.80 48.20

65.40 82.20 89.00 32.40 66.20 54.60 48.00

71.80 90.20 89.20 32.80 66.80 55.00 55.60

76.60 88.40 89.40 32.60 66.60 54.80 48.20

72.40 90.20 96.80 45.60 87.20 57.40 48.20

74.60 94.52 97.20 47.80 91.80 65.40 60.00

Avg

62.60

62.54

65.91

65.23

71.11

75.90

Table 13: Per-component ablation atop GEPA: adding one ESPO component at a time. Averaged across the 7 main benchmarks; single-seed values (component variants were not rerun over 3 seeds). Avg Len is character count of the final prompt. Configuration GEPA GEPA + multi-strategy GEPA + bootstrap select GEPA + full-error diagnose ESPO (all three)

D.5

The length metric is more revealing: any single addition to GEPA leaves prompt length at, or slightly above, the GEPA baseline (multi-strategy alone grows to 1,924 chars because diversified proposals without a diagnosis constraint accumulate reAvg Acc (%) Avg Len (chars) dundant rules). Only the full three-way combination simultaneously raises accuracy and cuts length 70.91 1,878 by −47%—evidence that solving prompt bloat re72.39 1,924 72.50 1,816 quires all three components together. 73.24

1,843

74.67

1,004

Per-Component Ablation atop GEPA

Table 4 in the main paper ablates ESPO components on Tweet only. Table 13 gives the complementary view: starting from GEPA and layering each ESPO component individually, averaged across all 7 main benchmarks. Multi-strategy alone contributes +1.48 pp, bootstrap-select alone +1.59 pp, and full-error diagnose alone +2.33 pp. Naive linear addition would predict ≈ 5.40 pp, whereas the full ESPO stack delivers 3.76 pp—component gains partially overlap (e.g., full-error diagnose and bootstrap both mitigate overfitting on the small validation set).

D.6

Sensitivity to Reflection-Model Choice

Section 4 fixes the reflection LLM to Claude Sonnet 4.5. To test whether ESPO’s gains depend on a strong reflection model, we swap it to the open-source Qwen2.5-32B-Instruct and rerun every LLM-proposal-based method (COPRO, MIPROv2, GEPA, ESPO); results in Table 14. Default and Bootstrap do not use an LLM proposer, so their numbers are identical to Table 1 and are listed only to align table structure. Absolute accuracies drop for every LLMproposal-based method under the weaker reflection model (Table 14), consistent with what GEPA reports: candidate quality depends on the proposer’s semantic capability. The key observation is that the ESPO–GEPA gap is preserved: Avg lead 4.29 pp

Table 14: Sensitivity to reflection-model choice: test accuracy (%) when the reflection / prompter LLM is swapped from Claude Sonnet 4.5 (Table 1) to the open-source Qwen2.5-32B-Instruct, keeping the student (Sonnet 4.5) and all other settings unchanged. Default and Bootstrap have no LLM proposer and are shown only to align table structure. Best per row in bold. Dataset

Default

Bootstrap

COPRO

MIPROv2

GEPA

ESPO (Ours)

Tweet MMLU GSM8K HotpotQA ScoNe HoVer PUPA

37.60 23.20 32.60 25.80 49.00 48.00 1.61

37.80 23.00 36.80 14.40 46.00 48.00 1.53

61.40 82.80 33.20 12.80 40.60 43.60 47.40

68.60 80.20 33.40 12.60 40.80 43.20 1.40

63.20 82.60 86.40 38.20 74.60 48.20 51.40

68.80 86.20 88.80 39.60 81.40 54.60 55.20

Avg

31.12

29.65

45.97

40.03

63.51

67.80

under Qwen2.5-32B, comparable to (and slightly larger than) the 3.76 pp headline under Sonnet 4.5 in Table 1. The ordering ESPO > GEPA > COPRO / MIPROv2 holds under both prompters, indicating that ESPO’s structural gains come from the three-phase design rather than from a single strong prompter. D.7

Open-Ended Generation Pilot: XSum

The main benchmarks are verifiable (classification / exact-match / F1). To probe whether ESPO transfers to open-ended generation—where prompt bloat matters most—we run a pilot on XSum summarization. Judge model: Claude Sonnet 4.5. Protocol: 200 test articles; ESPO and GEPA are optimized on identical train/val splits from XSum; at test time, each summary pair is judged pairwise with randomized output order and method identity hidden from the judge. Results: ESPO wins 58.0%, ties 22.0%, loses 20.0% against GEPA. Final prompt length is 720 chars (ESPO) vs. 2,180 (GEPA), a 67.0% reduction. This is a preliminary sanity check; a full open-ended benchmark suite (long-form QA, code generation, dialogue) is future work. Because ESPO’s Diagnose stage currently assumes ground-truth error labels, extending diagnosis to judge-based signals is a natural next step, listed as a limitation. D.8

Cluster Stability

Section 3.2 describes clustering as “implicit” (LLM-based). We add two direct evaluations of clustering quality: • Test–retest agreement. We invoke the reflection LLM three times independently on the same error set and, for each error, check whether it is assigned to semantically equivalent clusters across the three calls.

• Human-verified purity. The authors randomly sample 50 error–cluster assignments across datasets and independently review whether each error sits in a semantically coherent cluster. Results: per-error agreement across 3 independent LLM calls is 82.4%; human-verified cluster purity on the 50 sampled errors is 88.0%. These indicate the LLM-based clustering is stable and semantically coherent enough for the Diagnose stage; residual noise is absorbed by the downstream Diversify + Select stages. D.9

Strategy Diversity Quantification

Assumption (A1) in Theorem 1 idealizes the four proposal strategies as independent, whereas in practice they share the same reflection LLM. We quantify the actual departure from independence empirically: for each pair of strategy-generated candidate prompts, we score both over 500 held-out examples to obtain two binary correctness vectors, and compute (i) Jaccard similarity (both-correct / atleast-one-correct)—overlap of correctly-answered items; (ii) Pearson correlation of the two correctness vectors—overall synchrony. Averaged across all candidate pairs: Metric (averaged over strategy pairs)

Value

Pairwise Jaccard similarity Pairwise Pearson correlation

0.62 0.48

A value of 1 means strategies are fully redundant; 0 means strictly independent. The observed values sit in between—strategy outputs are partially decorrelated, so candidates from different strategies exhibit substantive diversity even when generated by the same LLM. This justifies treating (A1) as an idealization rather than a literal claim: the exploration-gain term in Theorem 1 is expected to √ shrink by a factor of 1 − ρ under correlation ρ,

and the observed correlation is bounded well below 1.

Ethical Considerations

E.1

Use of LLMs.

ESPO uses commercial and open-weight large language models (Claude Sonnet 4.5 as reflection LLM and student model in the main experiments; Gemma 3 12B, Mistral 14B, Qwen3 32B, and Claude Haiku 4.5 as additional students). Inference costs and emissions scale with the number of optimization rounds and bootstrap evaluations; we report token costs in Table 10 so that practitioners can estimate environmental impact and budget. E.2

Bias propagation.

Prompt optimization that drives accuracy up against a static benchmark may inherit or amplify any biases present in (1) the training/validation examples used for diagnosis, (2) the reflection LLM’s clustering of errors, and (3) the metrics used for selection. ESPO’s structured diagnosis surfaces error categories explicitly, which can aid auditing, but it does not guarantee that bias-related failure modes will be identified or corrected. We recommend that downstream users evaluate optimized prompts on bias-relevant slices before deployment, especially for socially sensitive applications. E.3

Benchmark contamination.

Several of the public benchmarks we use (Tweet, MMLU, GSM8K, HotpotQA, ScoNe, HoVer, PUPA) may overlap with LLM pre-training data. Our experimental design holds this contamination risk constant across all optimizers (Default, Bootstrap, COPRO, MIPROv2, GEPA, ESPO), so the relative improvements we report are not driven by ESPO seeing more contaminated data. Absolute accuracy numbers should be interpreted with the standard contamination caveats for each benchmark. E.4

Dual-use considerations.

The techniques in ESPO are general promptoptimization tools and could be applied to objectives we did not study, including ones with negative downstream impact (e.g., optimizing prompts to bypass safety filters). We release code and prompts for the public NLP benchmarks studied in this paper; we do not release prompts or configurations targeted at evading safety mechanisms.

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

Analyze & explore related research in Conceptio

Related documents