SPLICE: Structured Prompt Local Iterative Combinatorial Evolution
Organizations: Amazon Web Services
Abstract
Natural language optimization (NLO) improves an agent by having a model critique and rewrite its natural language policy parameters: system prompts, tool instructions, reasoning directives, few-shot demonstrations. These artifacts are multi-section documents in which some sections encode contracts (safety clauses, tool schemas, output formats) that must not drift, while others are legitimate optimization targets. Most iterative NLO methods treat the artifact as a single editable string, producing three recurrent failure modes: unsafe global rewrites, beam collapse onto a single lineage, and unchecked bloat, none addressed by formal guarantees. We introduce SPLICE, a unified NLO framework that poses optimization as constrained combinatorial search over an edit graph of block-structured, selectively-mutable states. We map each failure mode to a matched guarantee: (i) per-block mutability preserves contract text verbatim, with a price-of-freezing bound; (ii) elitist beam search with diversity slots never lets the leader regress on validation, bounds regression under noisy re-evaluation by an exponential tail, and keeps a competitive candidate from a different parent whenever one exists; (iii) a ratio length regularizer comes with an explicit accuracy-length bias bound. Candidates are proposed from dual section-local textual gradients; under a proposer-competence condition whose proxy we measure, edit-graph reachability and a convergence rate bound how quickly improving children arrive. Across seven public benchmarks under five reproduced protocols, SPLICE wins on four and matches the strongest prior method on three. On a production-style contract stress test it keeps the contract clauses that unconstrained optimizers trade away to raise the proxy metric, and ablations attribute gains to critique and elitist search.
Figures & tables
| Optimizer | ARC | GSM8K |
|---|---|---|
| Task Description | 79.7 | 59.4 |
| Expert Prompt | 78.4 | 78.9 |
| Llama Prompt | 89.7 | 79.5 |
| CoT | 79.4 | 76.3 |
| OPRO | 79.1 | 77.1 |
| ProTeGi | 78.8 | 77.3 |
Appendix figures & tables32 assets
Supplementary material from the paper’s appendix.
Appendix
| Result | What it says | Rests on | Cov. |
| Hold whether or not the proposer is competent | |||
| Prop. 3 | Diameter. Any two states are at most edits apart | connected ordering moves | ✗ |
| Lem. 1 | Leader. The leader’s score never decreases | cached scoring, parent retention | ✗ |
| Prop. 5 | Beam vs greedy. The elitist leader scores at least greedy’s state until the beam drops that state | coupled draws, per-state cache | ✗ |
| Thm. 1 | Diversity. If a competitive child of another parent exists, the beam keeps one | a qualifying candidate in | ✗ |
| Prop. 1 | Gate. The quality gate never falls | Lem. 1 , per-state cache | ✗ |
| Method | Gemma-3-27B | DeepSeek-V3.2 |
|---|---|---|
| Baseline | 44.6 | 56.0 |
| AutoDiff | 55.7 | — |
| OPRO | 56.0 | — |
| EvoPrompt | 53.3 | 56.6 |
| GEPA | 42.0 | — |
| CAPO | 56.3 | — |
| Contract class | Instantiation | Costs reward? |
|---|---|---|
| Tool schema | record_sentiment : enum-constrained label, | ✗ |
| additionalProperties: false | ||
| Safety text | no input echo; no chain-of-thought; | ✗ |
| prompt-injection resistance | ||
| Output contract | lone JSON envelope, no surrounding prose | ✗ |
| Business rule | Policy-1 compliance routing | ✓ |
| Example | Output | Proxy | Contract |
|---|---|---|---|
| ESCALATE | |||
| label, correct | |||
| label, wrong | |||
| label, correct | |||
| label, wrong | |||
| ESCALATE |
| Arm | Cands. | Verbatim | Reworded | Deleted | Mod. rate |
|---|---|---|---|---|---|
| A0 seed (no optimization) | 3 | 3 | 0 | 0 | |
| A1 Splice (contract frozen) | 456 | 456 | 0 | 0 | |
| A2 all-mutable | 336 | 6 | 107 | 223 | |
| A3 monolithic | 372 | 44 | 316 | 12 | |
| A4 soft-instructed | 408 | 111 | 297 | 0 |
| Val acc. | Test acc. | Escalation | |
|---|---|---|---|
| Arm | (proxy) | (contract-aware) | compliance |
| A1 Splice (contract frozen) | |||
| A2 all-mutable | |||
| A3 monolithic | |||
| A4 soft-instructed |
| Strategy | Best search score ∗ | Step of best | ||
|---|---|---|---|---|
| div3 | ||||
| div2 | ||||
| div1 | ||||
| div0 | ||||
| elitist_fullbatch ‡ |
| Arm means (3 seeds) | Paired | ||||
|---|---|---|---|---|---|
| Arm | Val acc. | Test acc. | Steps | Prop. win | val |
| off | |||||
| on, | |||||
| on, (control) | — | ||||
| on, | |||||
| GPQA-Diamond, by target tier | ||||
|---|---|---|---|---|
| SST-5 | Frontier | Large | Small | |
| step | ||||
| step – | – | |||
| tier mean (step ) | — | |||
| proxy at tier mean, | — | |||
| Method | Prompt tok/ex | Completion tok/ex | Total tok/ex |
|---|---|---|---|
| Baseline (no optimization) | |||
| GEPA | |||
| ContraPrompt | |||
| Splice |
| Strategy | Models | Val (%) | Train (%) | Gap | Tok. (K) |
|---|---|---|---|---|---|
| Greedy ( ) | 6 | 342 | |||
| Beam ( ) | 6 | 1,394 | |||
| Elitist Beam | 6 | 1,060 | |||
| BoN ( ) | 6 | 26 | |||
| BoN ( ) | 6 | 34 | |||
| BoN ( ) | 6 | 44 |