PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.04197v1cs.CLcs.AI

TL;DR

Evolutionary prompt optimizers can produce bloated prompts because they incompletely observe errors, explore narrowly, and select unreliably. ESPO addresses these issues with Diagnose, Propose, and Select phases, improving average benchmark accuracy while shortening prompts; its selection cost and reflection-model assumptions remain scope boundaries.

  • Problem

    Evolutionary prompt optimization suffers from prompt bloat and three structural deficiencies: incomplete error observation, limited search diversity, and unreliable selection.

  • Method

    ESPO diagnoses all training errors, generates candidates through four complementary strategies, and applies bootstrap stability selection.

  • Results

    74.67% average accuracy versus 70.91% for GEPA (+3.76 pp) was achieved across seven benchmarks with prompts 47% shorter.

  • Takeaways & Limitations

    ESPO matched or exceeded GEPA across the seven benchmarks while combining higher accuracy with shorter prompts and lower inference latency.

  • Takeaways & Limitations

    A full ESPO run with K=4, B=20, and N=10 costs roughly the same as one GEPA run because bootstrap selection requires candidate-resample evaluations.

Abstract

from arXiv · show

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

1 Introduction

ESPO reframes prompt optimization as structured statistical estimation to address prompt bloat caused by incomplete error observation, limited search diversity, and unreliable selection. Its three-phase design combines complete error diagnosis, complementary candidate generation, and bootstrap selection.

  • Evolutionary optimizers such as GEPA replace manual prompt trial-and-error with evaluation, reflection, mutation, and survivor selection.
  • Prompt bloat arises because iterative optimization appends rules and caveats, increasing length without reliably improving accuracy.The paper attributes this pattern to incomplete error observation, limited search diversity, and unreliable selection.
  • ESPO diagnoses all training errors into 3–7 structural patterns in one round, improving coverage over small random error samples.
  • ESPO proposes candidates through four complementary strategies and selects among them with bootstrap stability selection.The strategies use different inductive biases, while selection targets robustness under validation-set noise.
  • Across seven benchmarks, ESPO averages 74.67% accuracy versus 70.91% for GEPA, while producing prompts 47% shorter.The contribution summary reports a +3.76 pp accuracy difference and prompt lengths of 1,004 versus 1,878 characters.

2 Related Work

Related work spans automated prompt search, evolutionary extensions, theoretical analyses, gradient or selection-based optimization, systematic error discovery, and bootstrap-based robust selection. ESPO connects these strands by combining structured failure analysis, diverse candidate generation, and resampling-based selection.

  • Automated prompt optimization methods use LLM generation, meta-prompting, Bayesian surrogates, or evolutionary procedures to reduce manual prompt engineering.
  • Recent evolutionary extensions add richer memory, multi-objective criteria, decomposed evolution, or unified frameworks, while theoretical work studies generalization bounds.
  • Gradient-based and selection-based methods refine prompts through textual gradients or best-arm identification, but structured error clustering remains distinct from these formulations.
  • Systematic error analysis discovers coherent failure modes through clustering, behavioral testing, and slice-based evaluation.
  • ESPO echoes generation-versus-selection prompting by generating diverse candidates and selecting among them with bootstrap resampling.
  • ESPO adapts bootstrap and stability-selection principles to choose candidates that repeatedly win across resamples rather than by chance on one validation split.

3 ESPO Framework

ESPO formulates prompt optimization as a three-phase pipeline: diagnose all training errors, generate diverse candidates, and select a robust prompt through bootstrap resampling. The framework links these choices to generalization terms and predicts that diversity requires reliable selection.

  • 3.1 Problem Formulation: ESPO seeks a prompt p* maximizing test performance for a task with training data, validation data, and metric M.
  • Phase 2: Propose: Phase 2 generates candidates with four complementary strategies: diagnostic revision, consolidation, ablation, and factual injection.The strategies target root causes, prompt length, over-triggered rules, and domain-specific factual context respectively.
  • Phase 2: Propose: Each strategy independently seeds candidates, followed by cross-pollination and targeted refinement within a population capped at N=10.No single strategy dominates across all datasets, supporting the framework’s independent-bias assumption.
  • Phase 3: Select: Phase 3 selects the candidate winning the most of B=20 bootstrap resamples, breaking ties in favor of shorter prompts.This targets multiple-testing noise from choosing among approximately 10 candidates on a validation set of about 30 examples.
  • Theoretical Motivation: The generalization analysis assigns bias, exploration, and selection terms to the three phases, while the ablation shows diversity without bootstrap selection reduces performance by −1.20%.The bound uses diversity for exploration and bootstrap resampling for selection precision; its assumptions include separation from validation noise.
  • Phase 1: Diagnose: Phase 1 collects all training errors and clusters them into 3–7 structural patterns whose descriptions, examples, and counts feed candidate generation.Full error coverage occurs in one round, unlike GEPA’s approximately 15 rounds to observe all patterns with 95% probability.

4 Experiments

Across seven benchmarks and multiple student models, ESPO recovers accurate, compact prompts from deliberately weak starting prompts. Its gains persist across models, while ablations attribute performance to structured diagnosis, proposal diversity, and bootstrap selection.

  • Main results: Non-reflective baselines fail to recover strong prompts from weak starts: Bootstrap reaches 29.65%, COPRO 50.93%, and MIPROv2 44.03%.These methods remain 20–30 pp behind GEPA/ESPO on average and near floor on PUPA.
  • Main results: Across seven benchmarks, ESPO averages 74.67% accuracy versus GEPA’s 70.91%, a +3.76 pp improvement, and is at least as accurate on every dataset.The paired ESPO−GEPA difference is significant at α=0.05.
  • Main results: ESPO prompts average 1,004 characters versus GEPA’s 1,878, a 47% reduction, while matching or lowering GEPA’s per-example inference latency on every task.On HotpotQA, ESPO uses 1,008 characters versus GEPA’s 2,845 with comparable accuracy.
  • Main results: Length control alone is insufficient: Constrained GEPA reduces prompt length by 38% but changes average accuracy by only +0.09% and degrades HotpotQA by −4.20%.ESPO combines concise prompts with higher accuracy through diagnosis, multi-strategy proposals, and bootstrap selection.
  • Cross-model generalization: Across Gemma 3 12B, Mistral 14B, Qwen3 32B, and Claude Haiku 4.5, ESPO achieves the best average accuracy for every student model.The largest average GEPA→ESPO gap is +9.20 pp on Qwen3; Qwen3 GSM8K rises from 35.40% with GEPA to 91.40% with ESPO.
  • Ablation study: Ablations show complementary components matter: Bootstrap adds +3.60%, Diagnose +2.00%, diversity alone hurts −1.20%, and all three together reach +6.18%.Sensitivity analysis finds K=4, B=20, and full-batch diagnosis provide the best accuracy–length trade-off.

5 Conclusion

ESPO recasts prompt optimization as structured statistical estimation through diagnosis, diverse proposal generation, and bootstrap selection. Across benchmarks and models, it improves accuracy while producing shorter prompts.

  • ESPO recasts prompt optimization from evolutionary search to structured statistical estimation through structured diagnosis, multi-strategy generation, and bootstrap stability selection.
  • +3.76 percentage points: ESPO reaches 74.67% average accuracy versus 70.91% for GEPA across seven public benchmarks.
  • 47% shorter prompts: ESPO produces 1,004-character prompts versus 1,878 for GEPA and is faster at inference.
  • ESPO matches or exceeds GEPA on every dataset and yields the best average accuracy across four additional student models.The additional models are Gemma 3 12B, Mistral 14B, Qwen3 32B, and Claude Haiku 4.5.
  • The largest reported cross-model gap occurs on Qwen3 GSM8K, where accuracy rises from 15.00% to 91.40%.

6 Limitations

ESPO’s evaluation and theory have practical and scope limitations, including optimization cost, shared reflection-model dependence, diagnosis coverage, and restricted task coverage. Its theorem relies on simplifying assumptions and is explanatory rather than a tight guarantee.

  • Optimization cost: A full ESPO run with K=4, B=20, and N=10 costs roughly the same as one GEPA run at default settings.Lowering B or N can reduce costs for practitioners with tighter budgets.
  • Single reflection model and independence: All reflection uses Claude Sonnet 4.5, so mixing reflection models across strategies is not explored.
  • Single reflection model and independence: ESPO’s independence assumption is simplified because all four candidate strategies share the same reflection LLM and therefore produce correlated distributions.The empirical exploration gain is reported as consistent with the bound under mild correlation.
  • Coverage of error patterns: Diagnosis may be incomplete when error patterns are more numerous or subtle, including distributional shifts rather than discrete modes.
  • Scope and reporting: Evaluation covers seven benchmarks but excludes tool use, long context, code, and multi-turn dialogue.The largest cross-model gains occur where the default prompt is far from the student’s prior.
  • Theoretical assumptions: Theorem 1 is an explanatory framework rather than a tight probabilistic guarantee and assumes independent strategies, sub-Gaussian validation noise, and p1 > 1/2.

A Full Proof of Theorem 1

Theorem 1 decomposes the generalization gap into a bias floor, exploration gain, and bootstrap-controlled selection error. Its lemmas show how multiple strategies improve candidate quality while resampling stabilizes selection, with GEPA as the K=1, B=1 case.

  • Theorem 1 models each candidate’s test accuracy as Acc*−b_k+ε_k and analyzes bootstrap selection among K independent strategies.
  • The proof decomposes the generalization gap into a bias floor, an exploration gain from order statistics, and a selection error controlled by bootstrap concentration.
  • E[max_k Acc_test(p_k)] is at least Acc*−min_k b_k+σ·Φ^-1(1−1/K), establishing a lower bound from the best strategy and search diversity.
  • Bootstrap plurality selects the true best candidate with probability at least 1−exp(−2B(p1−1/2)^2) when p1>1/2.
  • The resulting selection-error accuracy loss is bounded by O(sqrt(ln K/(n_val·B))), combining validation estimation, bootstrap confidence, and a multiple-testing correction.
  • For GEPA’s K=1 and B=1 configuration, the exploration gain vanishes and selection error remains O(1/sqrt(n_val)).

B Supporting Analysis: Error Pattern Coverage

The supporting analysis argues that full-batch diagnosis covers error patterns in one round, then feeds structured failure patterns into diverse proposal strategies and bootstrap selection. The chosen settings trade coverage, diversity, robustness, and cost.

  • Error pattern coverage: T=⌈n·ln(K*/δ)/(m·min_k n_k)⌉ rounds suffice to observe all K* error patterns with probability at least 1−δ.
  • Error pattern coverage: For K*=5, m=3, n=20, and min_k n_k=2, GEPA requires approximately 15 reflection rounds for 95% coverage, whereas full-batch diagnosis achieves coverage in one round.
  • Structured diagnosis: The reflection model converts all training errors into 3–7 named patterns with root causes, member indices, and suggested instruction fixes.
  • Structured diagnosis: The Tweet example shows diagnosis distinguishing sports reporting and entertainment commentary from subjective sentiment, with pattern-specific fixes.
  • Structured diagnosis: The structured diagnosis replaces reflection on three random errors and lets proposal strategies target root causes rather than symptoms.
  • Candidate generation: ESPO generates candidates through diagnostic revision, consolidation, ablation, and factual injection, each using a different error-fixing strategy.
  • Bootstrap selection: Bootstrap selection evaluates all candidates on 20 resamples and chooses the candidate with the most wins, breaking ties in favor of shorter prompts.
  • Hyperparameter settings: K=4, B=20, and N=10 were fixed before experimentation to balance distinct inductive biases, selection reliability, and computational cost.

C.5 Hyperparameter Sensitivity Analysis (Extended)

The analysis varies bootstrap resampling, diagnosis batch size, and proposal-strategy diversity to test how ESPO’s components affect accuracy, prompt length, and robustness. Full-error diagnosis and diverse strategies matter because no single proposal strategy dominates across benchmarks.

  • Bootstrap resampling: 74.80% accuracy with B=20 or B=30 selects a shorter, more robust cross-pollination candidate, whereas B≤5 selects a longer ablation candidate.B=1 gives 73.80%; B=5 and B=10 give 74.00%.
  • Strategy diversity: No single proposal strategy dominates: diagnostic revision wins on Tweet, consolidation on HotpotQA, and factual injection wins on HoVer and PUPA.Ablation ties with diagnostic on MMLU and with consolidation/factual on GSM8K.
  • Strategy diversity: The observed strategy differences support the independent-bias assumption underlying the exploration-gain term in Theorem 1.The evidence is empirical rather than a literal claim of independence.

D.2 Inference Latency and Training Cost

ESPO reduces inference latency and optimization-time reflection usage while retaining accuracy across students and initialization settings. Its strongest reported gains include shorter prompts under strong seeds and large cross-model improvements on Qwen3 GSM8K.

  • Cost and latency: ∼39% of GEPA’s reflection token usage is required by ESPO, whose structured diagnosis produces information-dense inputs.ESPO matches or improves GEPA’s inference latency on every benchmark, with the largest reductions on chain-of-thought tasks.
  • Variance and robustness: ESPO’s 3-seed mean gap over GEPA is 3.81 pp, close to the 3.76 pp headline comparison.The reported per-dataset gaps on HotpotQA and PUPA fall within one standard deviation.
  • Initialization robustness: 4.79 pp is ESPO’s average lead over GEPA under strong initialization, exceeding the 3.76 pp lead from the weak seed.Under strong initialization, GEPA keeps appending marginal rules while ESPO targets the remaining structural gap.

D.5 Per-Component Ablation atop GEPA

Ablations show that ESPO’s three components contribute overlapping gains, while the complete combination is needed to reduce prompt length. Additional analyses support strategy diversity, robustness to reflection-model choice, and a preliminary transfer to open-ended generation.

  • Component ablation: 3.76 pp is the full-stack gain over GEPA, below the ≈5.40 pp predicted by naively adding the individual component gains.Full-error diagnosis, bootstrap selection, and multi-strategy contribute +2.33, +1.59, and +1.48 pp individually.
  • Component ablation: −47% prompt length is achieved only by the full three-way combination; multi-strategy alone grows prompts to 1,924 characters.The result supports combining diagnosis, diversity, and selection to address prompt bloat.
  • Reflection-model sensitivity: 4.29 pp is ESPO’s average lead over GEPA with Qwen2.5-32B-Instruct as reflection model, preserving the ordering ESPO > GEPA > COPRO / MIPROv2.Absolute accuracies drop for all LLM-proposal methods under the weaker reflection model.
  • Open-ended generation: 58.0% of XSum pairwise judgments favor ESPO versus 20.0% favoring GEPA, with prompts of 720 versus 2,180 characters.This is a preliminary pilot; extending diagnosis to judge-based signals is identified as a limitation.
  • Clustering quality: 82.4% per-error agreement and 88.0% human-verified purity indicate stable, semantically coherent LLM-based clustering.Residual clustering noise is absorbed by the downstream Diversify + Select stages.
  • Strategy diversity: 0.62 pairwise Jaccard similarity and 0.48 Pearson correlation show strategy outputs are partially decorrelated despite sharing one reflection LLM.The observed correlation is bounded well below 1, supporting diversity as an idealized exploration assumption.

E.3 Benchmark contamination.

The paper cautions that benchmark contamination may affect absolute accuracy, while relative comparisons are held under the same contamination risk. It also notes that ESPO’s general prompt-optimization tools could be applied to harmful objectives outside the study.

  • Benchmark contamination: Several benchmarks may overlap with LLM pre-training data, so absolute accuracy should be interpreted with standard contamination caveats.The experimental design holds this risk constant across all optimizers, so relative improvements are not attributed to greater exposure by ESPO.
  • Dual-use considerations: ESPO’s general tools could be applied to negative downstream objectives, including bypassing safety filters.The authors do not release prompts or configurations targeted at evading safety mechanisms.
Loading 2609.04197v1…