PaperlayerView exact revision on arXiv

Source-linked AI summary

SEPO: Evidence-Grounded Prompt Optimization via Structural Editing

Xiaoyu Ma, Haoyue Liu, Yiwen Li, Jionghao Zhu, Zhichao Wang, Ye Chen, Xiaoying Tang

arXiv:2608.28067v1cs.AI

TL;DR

Existing API-only prompt optimisers rewrite prompts as opaque strings, obscuring where edits occur and which examples they help or harm. SEPO instead performs local structural edits with edit-effect lineage feedback, and across 14 tasks it outperforms GEPA while occupying both optimisation-time and test-time Pareto frontiers.

  • Problem

    Existing API-only prompt optimisers leave full-prompt diffs that do not identify relevant edit locations, reasons, or affected examples.

  • Method

    SEPO locally edits stable typed units in a two-layer prompt schema and carries example-linked edit-effect lineage records forward on each search branch.

  • Results

    61.9/73.3% macro accuracy on Llama/Qwen represents +3.1/+2.2 pp over GEPA across 14 tasks, while SEPO lies on both optimisation- and test-time Pareto frontiers.

  • Takeaways & Limitations

    SEPO yields a stronger accuracy–cost trade-off, using 2.9M optimisation tokens versus 4.1M for GEPA and producing prompts over 5× shorter.

  • Takeaways & Limitations

    Whether SEPO’s efficiency extends to substantially longer prompts or more compositional multi-step agentic skills remains open, and evaluation is limited to single-turn, single-call, text-based tasks.

Abstract

from arXiv · show

Existing API-only prompt optimisers are often described as interpretable, but in practice, this usually means only post-hoc inspectability: each iteration still rewrites the prompt as one opaque string, leaving a trace of full-prompt diffs rather than localisable, machine-readable edits. This paper introduces SEPO (Structural, Evidence-grounded Prompt Optimization), a multi-trajectory prompt optimiser centred on edit-effect lineage feedback. Rather than treating each iteration as an isolated whole-prompt rewrite, SEPO locally edits stable, typed units in a two-layer prompt schema, links the target and realised structural operations of each edit to the examples it newly fixes or breaks, and carries this edit-effect record forward to guide later architect calls on the same search branch. This makes prompt optimisation addressable, attributable, and actionable. Across a 14-task held-out suite, SEPO improves over the strongest baseline, GEPA, by 3.1 pp on Llama-3.1-8B-Instruct and 2.2 pp on Qwen3-8B, reaching 61.9% and 73.3% macro accuracy. SEPO also lies on both the optimisation-time and test-time Pareto frontiers, spending 2.9M optimisation tokens versus 4.1M for GEPA and producing prompts over 5x shorter.

1 Introduction

SEPO addresses the opacity of whole-prompt rewriting by making local edits to structured prompt units and linking each edit to examples it fixes or breaks. Across 14 held-out tasks, it improves accuracy over GEPA while using fewer optimisation tokens and shorter prompts.

  • Motivation: Most API-only optimisers rewrite the entire prompt as one opaque string, so diffs do not localise what changed or explain its example-level effects.This limitation remains whether rewrites use text-gradient feedback or LLM-as-optimiser sampling.
  • Method: SEPO targets stable typed units in a two-layer prompt schema and carries edit-effect records into later architect calls on the same branch.The record links targeted and realised operations to examples newly fixed or broken.
  • Evaluation: Under a matched 2000-metric-call budget, SEPO matches or exceeds six API-only baselines across both worker models, winning at least 11/14 tasks against every baseline.The evaluation uses a 14-task held-out suite spanning reasoning, coding, multi-hop question answering, and multidomain tasks.
  • Efficiency: SEPO spends 2.9M optimisation tokens versus 4.1M for GEPA and produces prompts over 5× shorter while remaining 6.9 pp above APSF.The comparison concerns optimisation and deployment trade-offs on the reported Pareto frontiers.

2 Related Work

Related prompt optimisers include monolithic rewriters, structure-aware factorised methods, and reflective or evolutionary searches with diversity. SEPO is positioned among approaches that expose structure, use feedback, and maintain diverse search trajectories.

  • Monolithic whole-prompt rewriting: Monolithic methods rewrite prompts as opaque strings under scalar validation rewards, using sampling, numerical feedback, gradient-free operators, or textual gradients.The cited examples include APE, OPRO, GrIPS, ProTeGi, and TextGrad.
  • Structure-aware factorised optimisers: Structure-aware factorised optimisers expose prompt components as first-class units through scaffolds, fixed templates, or predefined decomposition taxonomies.These methods optimise modules, sections, or task facets rather than only a single undifferentiated prompt string.
  • Reflective and evolutionary search with diversity: Reflective and evolutionary approaches combine natural-language feedback or population diversity to improve iterative prompt search.Examples include Self-Refine, ProMST, Evo-Prompt, Promptbreeder, GEPA, and PromptAgent.
  • SEPO’s position: SEPO’s iteration uses archive-based parent selection, lineage-aware evidence, attribution and patch architects, and example-level child gating.The workflow is summarised as a per-iteration process rather than as a single rewrite.

3 Method

SEPO optimizes prompts through structured, local edits whose targets and example-level effects are recorded and carried forward across search trajectories. Its method combines typed schema editing, shared evidence packets, regression-aware admission, and diversity-preserving parent selection.

  • Method overview: SEPO applies one local edit per iteration to a structured prompt and records its example-level outcomes as an edit-effect lineage state.The state makes optimization auditable and provides reusable feedback for later edits on the same search branch.
  • Prompt representation: A two-layer schema represents a global outline and step-local rules, giving each edit a stable, addressable target without fragmenting context.The attribution architect identifies either an edit within one outline step or a structural outline change, while the patch architect revises the schema.
  • Lineage-guided editing: Each iteration uses an attribution call to identify a typed target and failure rationale, followed by a patch call that emits a revised schema.Targets include editing, adding, splitting, or dropping steps, or rewriting the entire outline.
  • Evidence packet: Both architect calls consume a shared minibatch containing focused failures, newly fixed examples, and training probes.Newly broken examples are weighted by archive agreement, while newly fixed examples preserve recent gains; when no regressions exist, the focus slot is omitted.
  • Lineage feedback: The lineage record stores the attributed target, inferred realized operators, breadcrumb, and newly fixed or broken examples for conditioning later edits.The record is carried forward only when the child becomes a parent on the same search branch.
  • Admission and selection: SEPO prechecks children on training probes, then admits passing candidates for unique coverage, shorter prompts, or higher parent-relative score.Lexicase selection is used with probability 0.8 and uniform random sampling with probability 0.2 to preserve specialists while retaining exploration.

4 Experiments

SEPO is evaluated against six API-only baselines on a 14-task held-out suite, with experiments covering effectiveness, mechanisms, behavioral scope, auditability, and cost-effectiveness. It achieves stronger accuracy across workers and task families while maintaining advantages across budgets, ablations, auditability, and efficiency.

  • Held-out effectiveness: 61.9% on Llama and 73.3% on Qwen, improving over GEPA by 3.1 pp and 2.2 pp, respectively.SEPO beats GEPA on 13/14 Llama tasks and 11/14 Qwen tasks, and wins at least 11/14 tasks against every baseline under both workers.
  • Behavioral scope: The gains span BBH, MBPP+, and reasoning families, with especially large improvements on procedural tasks such as Word Sorting and MBPP+.On Word Sorting, SEPO is best under both workers; the Llama result is 58.2% with a +18.9 pp margin over GEPA.
  • Budget behavior: At every metric-call budget shown in Figure 3, SEPO remains at or above every baseline, so its lead is not confined to the 2000-call endpoint.The figure reports test accuracy at budgets 0, 500, 1000, 1500, and 2000.
  • Auditability and edit behavior: SEPO’s edits remain overwhelmingly step-local and composite, combining rule additions with pruning or refinement rather than merely accumulating prompt content.Its audit log records typed edit targets, operations, and effects, supporting retrospective inspection and later edit guidance.
  • Cost-effectiveness: ρ=4.37, exceeding MPO’s 2.65 and GEPA’s 2.36, while SEPO uses 2.59M worker optimisation tokens versus GEPA’s 3.88M.SEPO also holds architect-side cost to 0.34M tokens per cell and deployment cost to 203k per cell.

5 Conclusion

The conclusion presents SEPO’s edit-effect lineage feedback and two-layer prompt schema as the basis for structured, addressable optimisation. Across 14 tasks and two workers, SEPO outperforms six API-only baselines and provides a stronger accuracy–cost trade-off.

  • Core mechanism: SEPO links each local edit’s target and realised operations to newly fixed or broken examples and reuses that record on the same search branch.Its two-layer prompt schema provides a stable, addressable implementation.
  • Conclusion: Across 14 tasks and two workers, SEPO beats six API-only baselines by 3.1 pp and 2.2 pp over GEPA.The conclusion also places SEPO on both optimisation-time and test-time Pareto frontiers.

Limitations

SEPO’s evaluation covers representative prompt lengths and instruction spaces, but its efficiency advantage beyond these settings remains unresolved. The paper also leaves broader task settings and cross-task transfer for future work.

  • SEPO’s efficiency advantage on substantially longer prompts or more compositional agentic skills remains open.The unresolved settings involve multiple steps, tool calls, or state tracking.
  • SEPO produces task-specialised artefacts because its schema is tailored per task, leaving cross-task transfer to future work.
  • The evaluation covers only single-turn, single-call, text-based tasks, while broader domains remain future work.The paper mentions agentic pipelines and multimodal prompts as possible broader domains.

A.1 Datasets, Splits, and Licences

The study evaluates optimisers on fixed, disjoint benchmark splits under a shared harness, deterministic worker inference, and common metric-call budgets. SEPO’s prompts and architect templates are task-agnostic at initialization but become task-specialised through optimisation.

  • Datasets and splits: The 14-task held-out suite spans BBH, MMLU-Pro, MBPP+, GSM-Hard, and HotpotQA, with fixed indices shared across methods and seeds.Reported fields include training-example counts, held-out test sizes, task metrics, and licences.
  • Datasets and splits: Every task uses a fixed training set and disjoint held-out test split, with evidence packets constructed from training data.This convention is applied uniformly across all five benchmark sources.
  • Evaluation protocol: The evaluation harness, worker models, data splits, metric-call budget, and random seeds are shared across optimisers.Workers are Llama-3.1-8B-Instruct and Qwen3-8B; each serves for optimisation-time scoring and held-out deployment.
  • Evaluation protocol: Worker inference is deterministic under fixed prompts and examples, using temperature 0.0, top-p 1.0, and a maximum generation length of 2,048 tokens.Held-out evaluation reuses the selected prompt and reports seed means with standard deviations.
  • Prompt setup: All runs begin from the same task-agnostic three-step seed schema with no step-local rules or benchmark-specific prompt priors.The first iteration therefore enters the no-regression fallback by construction.
  • Architect templates: SEPO’s attribution call selects a typed target and rationale, while its patch call emits one revised schema using the shared evidence and lineage context.The attribution call does not itself rewrite the schema.

C.2 Operator Label Space

SEPO represents edits with an operator vocabulary divided between rule-layer and outline-layer changes, then infers realised labels from deterministic parent–child structural diffs. The evidence packet and breadcrumb preserve example-level edit effects for subsequent decisions.

  • Operator decomposition: The operator vocabulary contains rule-layer and outline-layer sub-operations over SEPO’s two-layer schema.Rule operations modify step-local rule lists; outline operations modify top-level structure or text.
  • Operator inference: The architect’s typed target pre-locates an edit, while the realised operator is recovered post-hoc from the structural diff.The target vocabulary includes step, ADD, SPLIT, DROP, and backbone forms.
  • Structural diff: DIFF deterministically aligns outline steps and greedily matches child rules to parent rules using sequence similarity and thresholds.The procedure records added, dropped, refined, and copied locations, with refine and merge thresholds of 0.55 and 0.40.
  • Structural diff: Merge detection requires distinctive vocabulary from both candidate parent rules, while a 0.95 similarity guard favours refinement when one parent nearly covers the child.
  • Operator inference: INFEROP emits one label per changed location, so a single patch can carry multiple operator labels.Consequently, per-operation shares can sum above 100%.
  • Evidence packets: The evidence minibatch uses focus, anchor, and train slots, sampling newly broken and newly fixed cases to condition attribution and patch decisions.When no newly broken examples exist, the focus slot is empty and the anchor and train slots remain.
  • Lineage breadcrumbs: The breadcrumb renders each non-empty prior diff bucket and anchors changes with content snippets rather than numeric rule identifiers.This keeps the current schema free of inline markers.

E.1 Cross-Task Schema Examples

SEPO’s converged schemas differ across tasks because their failure modes differ, while retaining a shared two-layer architecture. The examples concentrate rules on task-specific requirements such as code extraction and implementation or question grounding and entity verification.

  • Cross-task schema patterns: SEPO’s converged schemas differ across tasks because their failure modes differ within the shared two-layer architecture.The examples demonstrate task-tailored rule distributions without imposing one universal distribution.
  • MBPP+: On MBPP+, rules concentrate on extraction and implementation, including function-name fidelity, type parsing, and constraint mapping.
  • HotpotQA Medium: On HotpotQA Medium, rules concentrate on grounding and entity verification.The schema instructs the worker to locate exact entities, verify matches, and avoid outside knowledge.
  • MBPP+: The MBPP+ schema requires complete Python functions, test calls using the provided assert statement, and an exact Answer: (X) final line.
  • HotpotQA Medium: The HotpotQA schema requires explicit multi-hop tracing across passages and stopping once the answer is reached.

E.2 Worked Iteration Trace: Discovering an Anti-Verification Rule

The trace shows SEPO discovering that self-verification caused worker loops and replacing it with an anti-reprocessing rule. Its lineage feedback links local edits to newly fixed or broken examples, enabling targeted repairs and continued branch improvement.

  • Self-verification failure: The iteration-26 self-verification rule was introduced to address sorting typos despite correct reasoning.The rule required strict side-by-side comparison and immediate resorting.
  • Self-verification failure: The new verification rule caused infinite repetition loops and false verification on newly broken examples.Ex #40 repeated “anaheim” hundreds of times, while Ex #7 produced an incorrectly sorted list.
  • Lineage feedback: The evidence packet combined focus regressions with train-probe examples, allowing one “stop re-processing” principle to address both failure types.The child retained an aggregate training score of 32/50 but solved an example unique to its branch and was admitted through unique contribution.
  • Anti-verification repair: At iteration 32, SEPO dropped both post-sort reprocessing rules and added a critical instruction to trust the single-pass sort.This edit repaired Ex #40 and #7 while removing the loop pathology.
  • Lineage feedback: SEPO uses regression repair when a parent breaks examples and a train-only fallback when it does not, preserving trajectory diversity through local operators and branch selection.The winning Word Sorting lineage accumulated edits through Add, Refine, Drop, and RewriteStep operations.

E.4 Failure-Mode Analysis

SEPO’s Word Sorting gains are bounded by input length: instructional rules repair systematic failures, but accuracy declines monotonically as lists become longer. Sensitivity and variance checks nevertheless preserve SEPO’s ranking advantage in the reported comparisons.

  • Length sensitivity: Accuracy falls monotonically with sort length, reaching 79% for lists of ≤5 words and 31% for lists of ≥16 words.The pattern held across every examined schema variant on a 100-example held-out diagnostic subset.
  • Length sensitivity: The schema repairs length-independent format, hallucination, and verification-loop failures but does not provide an algorithmic execution mechanism for long inputs.Its instructional rules raise the probability of a correct single pass, while per-token errors compound with list length.
  • Robustness checks: Across 15 additional paired comparisons on five high-variance tasks, SEPO won 12 and had a higher six-run mean on every task.These runs supplement the main comparison with additional Llama seeds.
  • Robustness checks: Replacing HotpotQA-Medium with Hard changed SEPO’s macro accuracy from 61.9% to 59.0% and GEPA’s from 58.8% to 55.9%, preserving SEPO’s 3.1 pp lead.The authors retain Medium under Llama because the Hard split has limited answer accessibility.

G.3 Per-Benchmark Token Cost

The token-cost analysis decomposes architect, worker-optimisation, and worker-deployment usage by method and benchmark. It supports reproducible dollar estimates while distinguishing measured totals from an estimated MPO input/output split and dated prices.

  • Pricing assumptions: The reported dollar results are tied to public list prices and the 2026-05-26 exchange-rate snapshot.Architect and worker prices are converted using 1 USD = 6.79 CNY.
  • Cost decomposition: Cost is computed across architect, worker-optimisation, and worker-deployment channels using corresponding list prices and measured token counts.The token-based efficiency ratio is provider-independent, while the dollar ratio covers all three billed channels.
  • Pricing assumptions: Architect output tokens are approximately six times as expensive as architect input tokens at the reported price snapshot.The analysis therefore separates input and output channels rather than using a single token price.
  • Pricing assumptions: MPO’s total costs are measured, but its unavailable input/output split is estimated from GEPA.Only MPO’s dollar estimate depends on this approximation.
  • Cost decomposition: Table 11 reports per-method input/output token totals, while Tables 12–14 break architect, worker-optimisation, and deployment costs down by benchmark.Aggregate MEAN rows cross-check against the main-paper Table 5 columns.

G.4 Per-Benchmark Budget-Matched Curves

Budget-matched curves compare each method’s stored best-so-far prompt at shared metric-call checkpoints. SEPO leads consistently on BBH and MBPP+, remains competitive on MMLU-Pro, and is evaluated under identical conditions.

  • Evaluation protocol: Each method is re-evaluated at metric-call checkpoints 0, 500, 1000, 1500, and 2000 using its stored best-so-far prompt.Checkpoint 0 is the shared seed prompt, and all methods use the same evaluation protocol.
  • Benchmark comparisons: SEPO leads consistently on BBH and MBPP+ across the budget-matched accuracy curves.BBH and MMLU-Pro values are means over their sub-tasks, while MBPP+, GSM-Hard, and HotpotQA are shown individually.
  • Benchmark comparisons: SEPO remains competitive on MMLU-Pro under the shared 2000-metric-call budget.The comparison uses identical conditions for SEPO and all baselines.
Loading 2608.28067v1…