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

AI summary

Overview

Research area: Natural Language Processing — automated prompt optimization for large language models, specifically the problem of how to search over natural-language instructions without letting prompts grow unboundedly.

Technical level: Intermediate. The paper is readable without background in optimization theory, but it assumes familiarity with prompt engineering, held-out validation sets, bootstrapping, and basic statistical notation (standard deviation, order statistics, generalization bounds).

Scope: The paper proposes and empirically validates ESPO, a three-phase prompt optimizer (Diagnose, Propose, Select), comparing it against GEPA and four other optimizers on seven NLP benchmarks and five student LLMs.

What This Paper Is About

Evolutionary prompt optimizers such as GEPA improve prompts by repeatedly reflecting on errors and appending new rules, but this produces "prompt bloat": prompts grow up to 3 times longer across iterations while accuracy stagnates or degrades. The authors trace the failure to three structural problems — incomplete error observation, limited search diversity, and unreliable selection on small validation sets — and propose ESPO, which replaces evolutionary search with a structured estimation procedure: cluster all training errors at once, generate candidates through four strategies with distinct biases, then pick the winner by bootstrap resampling.

Key Contributions

1. A three-phase framework (Diagnose–Propose–Select) that reformulates prompt optimization as structured statistical estimation rather than evolutionary search. The paper shows that setting proposal strategies K=1, bootstrap resamples B=1, and diagnosis batch size m=3 exactly recovers GEPA, making the evolutionary paradigm a degenerate special case.

2. A generalization bound whose three terms — bias floor, exploration gain, and selection error — each correspond to one phase, supported by three lemmas (bias reduction via diversity, exploration gain via order statistics, and selection precision via bootstrap).

3. Empirical results on seven public benchmarks (Tweet, MMLU, GSM8K, HotpotQA, ScoNe, HoVer, PUPA) starting from a deliberately weak prompt, showing an average of 74.67% accuracy versus 70.91% for GEPA (+3.76 pp) with prompts 47% shorter (1,004 vs. 1,878 characters).

4. Cross-model generalization evidence on four additional student models (Gemma 3 12B, Mistral 14B, Qwen3 32B, Claude Haiku 4.5), where ESPO achieves the best average accuracy on every model tested.

Main Findings

• Non-reflective optimizers cannot salvage a weak starting prompt. Averaged over the seven datasets, BootstrapFewShot scores 29.65% (slightly below the 31.12% unoptimized default), COPRO scores 50.93%, and MIPROv2 scores 44.03% — 20 to 30 percentage points behind GEPA and ESPO. The authors conclude these methods need a reasonably good starting prompt to be effective.

• ESPO beats GEPA on average and matches or exceeds it on every dataset. Average accuracy 74.67% vs. 70.91% (+3.76 pp). The paired standard error of the ESPO-minus-GEPA difference across the 7 datasets is approximately 1.2 pp, making the average gap roughly 3.1 times its standard error (paired t-test significant at α=0.05). Outside-noise wins (>1σ) are HoVer (+8.80), Tweet (+6.18), MMLU (+4.92), and ScoNe (+4.40); within-1σ results are treated as ties: GSM8K (tie at ceiling), HotpotQA (+0.80), and PUPA (+1.20).

• ESPO's prompts are substantially shorter. Average length 1,004 vs. 1,878 characters (47% shorter). On HotpotQA, GEPA grows to 2,845 characters while ESPO stays at 1,008 characters at comparable accuracy (44.00% vs. 44.80%). The paper also reports equal or lower per-example latency than GEPA on every task, with the largest reductions on chain-of-thought tasks, though the specific latency values (Table 9) are not shown in the provided content.

• Length control alone does not explain the gains. A "Constrained GEPA" variant with a compact proposer instruction and max_length_ratio = 1.2 shortens prompts to 1,171 characters (a 38% reduction from 1,878) but moves average accuracy by only +0.09% (71.00% vs. 70.91%) and degrades HotpotQA by 4.20%. The authors argue that without structured diagnosis, the constraint prunes essential and redundant rules indiscriminately.

• The ablation confirms the theory's prediction that diversity without bootstrap selection hurts. On Tweet (GEPA baseline 68.60%): Bootstrap only gives +3.60%, Diagnose only +2.00%, Diversity only −1.20%, Diagnose+Diversity +2.00%, Diagnose+Bootstrap +2.20%, Diversity+Bootstrap −1.00%, and all three +6.18% (74.78%). The authors describe the +6.18% as exceeding the sum of any pair, indicating that better candidates require better selection.

• ESPO wins on every additional student model tested. Table 3 averages: Gemma 3 12B (ESPO 66.50 vs. GEPA 63.71), Mistral 14B (62.42 vs. 59.14), Qwen3 32B (68.51 vs. 58.91), Claude Haiku 4.5 (70.15 vs. 67.98). Note that the Table 3 values for Qwen3 differ from the numbers quoted in the body text, which states ESPO 68.31% and GEPA 59.11% and describes the largest GEPA-to-ESPO average gap as +9.20 pp on Qwen3.

• The Qwen3 GSM8K result is the headline cross-model case. Accuracy moves from 15.00% (default) to 35.40% (GEPA) to 91.40% (ESPO), which the paper describes as +56.00 pp over GEPA. The authors attribute this to structured diagnosis identifying an output-format mismatch that rule accumulation only partially addresses.

• No single proposal strategy dominates. Seed-phase validation accuracy shows diagnostic revision winning on Tweet, consolidation on HotpotQA, ablation tying on MMLU and GSM8K, and factual injection winning on HoVer and PUPA — the authors cite this as evidence for the independent-bias assumption behind their bound.

• Hyperparameters are not sharply tuned. Accuracy varies by at most 5% across settings, within the reported confidence interval. The defaults (K=4, B=20, m=all) give the best accuracy–length trade-off; K=4 is 32% shorter than K=3 at comparable accuracy (774 vs. 1,134 characters), and full-batch diagnosis yields both the highest accuracy and the shortest prompt.

• Reflection cost is lower. ESPO's reflection tokens are approximately 39% of GEPA's, which the authors attribute to more information-dense inputs from structured diagnosis. A full ESPO run (K=4, B=20, N=10) on the 70/30/500 split costs roughly the same as one GEPA run at default settings.

Methodology in Plain English

The researchers start every method from the same intentionally weak prompt (for example, a one-sentence instruction telling the model to lean "negative" on Tweet, or "Refuse to answer" for PUPA). Each weak prompt was chosen as the lowest-accuracy option on a 30-example validation probe from a small candidate pool, and the authors state none was written to favor any optimizer. This setup tests whether an optimizer can recover a good prompt from a bad one, rather than polish an already-good one.

Each dataset is split into 70 training examples, 30 validation examples, and 500 held-out test examples. The default student model is Claude Sonnet 4.5 at temperature 0; the reflection LLM is always Claude Sonnet 4.5 at temperature 0.7.

ESPO then runs three phases:

1. Diagnose. Collect all training errors under the current prompt, and have a reflection LLM cluster them into 3 to 7 structural patterns, each with a description, representative examples, and a count. This contrasts with GEPA, which reflects on only 3–8 random errors per round; the authors use a coupon-collector argument to claim that the smaller sample needs roughly 15 rounds to see all patterns with 95% probability.

2. Propose. Generate candidates using K=4 complementary strategies, each conditioned on the diagnosis: diagnostic revision (fix root causes of each pattern), consolidation (rewrite without increasing length), ablation (soften or remove over-triggered rules causing false positives), and factual injection (extract domain knowledge from error examples). A seed phase produces 4–6 candidates; then two rounds of cross-pollination and targeted refinement are applied to top candidates, with the population capped at N=10.

3. Select. Draw B=20 bootstrap resamples of the 30-example validation set (sampling with replacement) and pick the candidate that wins the most resamples, breaking ties in favor of shorter prompts. The rationale is that point estimation over roughly 10 candidates on roughly 30 examples is a multiple-testing problem where a verbose candidate can rank first by noise.

The authors also derive a generalization bound decomposing the test-time gap into a bias floor, an exploration gain, and a selection error, showing that each phase tightens one term. They state two caveats: the constant under the O(·) in the selection term is shared between GEPA and ESPO, so the approximately 3.8× comparison reflects the sqrt(ln K / B) ratio rather than absolute magnitude; and Lemma 3's premise that the true-best candidate wins each resample with probability greater than 1/2 holds only when the best is separated from runners-up by more than the validation noise scale, which they describe as their empirical regime but not certified per dataset.

Why This Matters

Impact on research. The paper reframes prompt optimization as a statistical estimation problem and shows that a widely used evolutionary optimizer is a special case of a more general framework, which gives the field a vocabulary (bias floor, exploration gain, selection error) for diagnosing why prompt search fails. It also connects prompt optimization to bootstrapping, stability selection, and the MDL principle, and provides a controlled comparison showing that prompt-length control alone is not sufficient for accuracy gains.

Real-world applications:

• Cheap prompt recovery for deployed LLM features. Teams that inherit a poorly written or generic system prompt could use the Diagnose–Propose–Select loop to recover a task-appropriate prompt rather than hand-tuning.
• Cost and latency reduction in production. ESPO's prompts are 47% shorter on average than GEPA's (1,004 vs. 1,878 characters), which the paper links to lower inference latency and lower token cost on every task tested.
• Small-model deployment. Because the biggest cross-model gain appears where the default prompt is far from the student's prior (Qwen3 GSM8K: 15.00% to 91.40%), the approach may help squeeze usable accuracy out of smaller or cheaper student models without retraining.
• Reliable optimization under tight evaluation budgets. Bootstrap selection targets settings where only a few dozen validation examples are available, which matches many practical labeling constraints.

Industry relevance. The work comes from AWS Agentic AI, and its framing — automated optimization of natural-language instructions rather than parameters — maps directly onto agentic and tool-using LLM products where prompt quality drives both accuracy and serving cost. The authors report that a full ESPO run costs roughly the same as one GEPA run at default settings, which matters for teams deciding whether optimization is worth the compute.

Future Directions

1. Mixed reflection models. All reflection uses a single LLM (Claude Sonnet 4.5 at T=0.7). The authors note that mixing reflection models per strategy is unexplored, and that Theorem 1's independence assumption is a simplification because candidate distributions across strategies are correlated through the shared LLM (measured empirically at pairwise Jaccard 0.62 and Pearson 0.48 over 500 held-out examples per candidate pair).

2. Handling more numerous or subtler error patterns. Diagnosis assumes the reflection LLM can cluster errors into 3 to 7 patterns; the authors flag that when patterns are more numerous or subtle — for example distributional shifts rather than discrete modes — diagnosis may be incomplete.

3. Broadening task scope. The evaluation covers classification, multi-hop QA, math, NLI, fact verification, and privacy-preserving generation. Tool use, long context, code, and multi-turn dialogue are explicitly out of scope and remain open.

4. Tightening the theory. Theorem 1 is presented as an explanatory framework rather than a tight probabilistic guarantee. Certifying the p₁ > 1/2 premise per dataset, and accounting for correlated rather than independent proposal strategies, would strengthen the bound's practical claims.

Target Audience

Researchers and practitioners working on automated prompt optimization, LLM agent design, and inference-cost reduction. The paper is most valuable to readers who already know GEPA or similar evolutionary prompt optimizers and want a structured alternative with a theoretical rationale; the ablation table and cross-model grid make it useful for engineering teams deciding between optimizers. Readers looking for a self-contained introduction to prompt optimization may need to consult the cited background works (APE, OPRO, MIPROv2, GEPA) first, and readers seeking detailed latency or cost figures (Tables 9 and 10, Appendix B) will need the full appendix, which is not included in the provided content.

Authors’ abstract

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%).