betaFeedback

WorksComputer Science

SPLICE: Structured Prompt Local Iterative Combinatorial Evolution

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.

Introduction

An LLM system’s behavior is a policy determined by its weights and its text: system prompts, agent instructions, tool descriptions, and the harness code around the model. With black-box access the weights are fixed, and the text is the only part of the policy that can be optimized. Natural language optimization (NLO) improves it by having a model repeatedly critique and rewrite it; the formulation applies to any block-structured text, our experiments optimize prompts, and we loosely call the text the prompt. Production prompts are multi-section documents (role framing, demonstrations, safety constraints, tool schemas, output specifications) in one token stream, so an edit to one section can alter behavior governed by another – a regression risk. Some sections are contracts that must not change, and every added token costs latency: the deployed problem is constrained.

Iterative prompt optimization, the most developed form of NLO, follows four directions: generate-and-select rewrites [83, 93], gradient-inspired refinement from textual feedback [15, 62, 70, 87], compile-time module-level search [39, 60], and evolutionary population methods [1, 25, 28]. They share two implicit commitments: every part of a candidate is open to editing, and a run is a loop that proposes, scores and keeps candidates. Left implicit, these leave three gaps. First, deployment requirements cannot be stated: no prior method exposes selective mutability as a property of the search space, and growth is rarely priced ([1] report MIPROv2 prompts ∼3×\sim3\times longer at lower accuracy). Second, representations, proposals and selectors are confounded across implementations, so methods cannot be compared component by component. Third, the search dynamics are untheorized: no monotonicity, no-collapse or length-bias guarantees. The field largely solves the unconstrained relaxation of a constrained problem (related work in detail: Section B).

We make both commitments explicit by posing NLO as constrained combinatorial optimization (Figure 1). A prompt is a block-structured state x=(v1,…,vm,π)x=(v_1,\ldots,v_m,\pi); primitive edits connect states into a finite edit graph; freezing a block is a feasibility constraint that makes every edit to it unreachable, and length is a priced penalty. This one move closes all three gaps: contracts and cost become part of the problem, existing methods become instances of one batched search template that differ in named components, and search over a finite graph under a noisy oracle admits guarantees whose assumptions can be named. The same propose–score–retain structure underlies self-improvement loops [68, 90, 91], where frozen blocks become invariants the loop cannot rewrite. SPLICE (Structured Prompt Local Iterative Combinatorial Evolution) is this framework together with its natural solver (Algorithm 1).

NLO as constrained combinatorial optimization

Figure 1. NLO as constrained combinatorial optimization. (1) An artifact is a sequence of blocks: mutable blocks are optimization targets, frozen blocks are contracts. (2) The feasible set X\mathcal{X} is an edit graph; a frozen block admits only its seed text, so editing it is not an edge. Drawn is one SPLICE run: the leader path, a lineage held by a diversity slot, and pruned children. (3) One step critiques, proposes kk edits to mutable blocks, scores children on DvalidD_{\mathrm{valid}} with length priced, and keeps the elites plus a child of a different parent. Frozen text is not frozen behavior (§ 4).

Contributions.

  • SPLICE, a unified view of NLO as constrained combinatorial optimization (§ 2), separating representation, proposal mechanism and selector, with contracts as a feasibility constraint and length as a penalty (Definition 11). Existing methods [1, 15, 60, 62, 70, 79, 83, 93] either instantiate a single batched iterative search template (Definition 14) or depart from it in a component we can name: the scoring set, the selector, the output rule, or the expansion (Section C); none treats a user-designated section as a constraint of the search.

  • The SPLICE solver, for the constrained problem (§ 2). Each production failure mode maps to one design choice: dual section-local critique edits only mutable blocks, a ratio length penalty prices bloat, and elitist selection reserves diversity slots against collapse.

  • A theory of search dynamics (§ 3). With no assumption on the rewards or the proposer, the beam leader’s validation score never regresses under cached scoring (Lemma 1), the beam keeps

StructureIterativeDualGradSecLocalElitismDiversityImmutablePricedTheory
APE [93]✗✗✗✗✗✗✗✗
OPRO [83]✗✓✗✗✓✗✗✗
ProTeGi [62]✗✓✗✗✗✗✗✗◐
MAPO [15]✗✓✓✗✗✗✗✗✗
MPO [70]✓✓✗✓✗✗✗✗✗
PO2G [47]✗✓✓✗✗✗✗✗✗
TextGrad [87]✗✓◐✗✗✗◐✗✗
DSPy [39]✓✓✗✗✗✗✗✗✗
MIPROv2 [60]✓✓✗✗✗✗✗✗✗
EvoPrompt [28]✗✓✗✗✓✓✗✗✗
Promptbreeder [25]✗✓✗✗✓✓✗✗✗
GEPA [1]✓✓✗✗✓✓✗✗✗
SPLICE (This Paper)✓✓✓✓✓✓✓✓✓

Table 1. Representative prompt optimizers against the axes exposed by our framework; Table 5 (Section B) covers every optimizer we discuss or compare against. ✓: the method directly provides the property; ✗: it does not; ◐: partial, or asserted but not established. “DualGrad”: positive and negative textual gradients. “SecLocal”: updates at the level of named prompt sections. “Elitism”: parents can survive a step. “Immutable”: designated sections are unreachable by any edit. “Priced”: prompt length enters the objective. “Theory”: formal guarantees about the search.

a competitive candidate from a different parent whenever one exists (Theorem 1), and the quality gate never loosens (Proposition 1). Assuming bounded rewards and i.i.d. batches, if candidates are instead re-scored on nren_{\mathrm{re}} fresh examples each step, the beam’s best score regresses by more than ε\varepsilon with probability at most W(1+k)exp⁡(−nreε2/cσ)W(1+k)\exp(-n_{\mathrm{re}}\varepsilon^2/c_{\sigma}), for a constant cσ≤2c_{\sigma} \le2 (Theorem 2 and Corollary 1). Assuming in addition a proposer whose edits improve with probability at least p⋆p^{\star} from every state ε\varepsilon-far from optimal (Assumption 1), a full beam with no ε\varepsilon-optimal member proposes an improving child in one step with probability at least 1−(1−p⋆)Wk1-(1-p^{\star})^{Wk} (Theorem 3), and the search reaches ε\varepsilon-optimality at a rate we give (Theorem 4). Finally, we price the constraints: freezing forfeits at most γ−1\gamma^{-1} times the frozen blocks’ best single-block gains (Proposition 2), and length regularization biases accuracy by at most λ⋅κ(x⋆)\lambda\cdot\kappa(x^{\star}) (Theorem 5).

  • Empirical validation (§ 4). On seven public benchmarks (SST-5 [75], GSM8K [14], AIME-2025 [4], ARC-Challenge [13], BBH [76], PUPA [73], GPQA-Diamond [64]) reproducing five published protocols [1, 37, 65, 89, 94] without modification, and calling a margin of at most 0.5 pp a match, SPLICE wins on four and matches the strongest prior method on three (top margin +5.1 pp on AIME-2025). On a contract stress test, unconstrained optimizers trade away the clauses SPLICE freezes, yet frozen text is not frozen behavior. Critique lifts Best-of-NN by +1.2–1.7 pp, and Elitist Beam leads the best plain Best-of-NN by +3.7 pp on SST-5 and +1.3 pp on GPQA (within noise).

Structured Prompt Local Iterative Combinatorial Evolution

We study NLO in the structured, black-box, sample-based regime. A practitioner has a fixed task over an input space I\mathcal{I} with unknown distribution P\mathcal{P}, a black-box LLM (Definition 7), a bounded reward (Definition 8), and an initial prompt (Definition 1) they wish to improve, using an i.i.d. training set D∼PN\mathcal{D} \sim\mathcal{P}^{N} to score candidates; a disjoint Dvalid\mathcal{D}_{\mathrm{valid}} scores candidates for selection (the proposer never sees its examples), and Dtest\mathcal{D}_{\mathrm{test}} is reserved for final reporting.

Prompts as Block-Structured States

The prompt is structured into semantically coherent blocks that can be rewritten independently; the goal is to pick one variant per block and an admissible ordering so as to maximise expected reward under P\mathcal{P} within a finite evaluation budget.

Definition 1 (Prompt Template). A prompt consists of m≥1m \ge1 blocks, indexed by [m]={1,…,m}[m] = \{1,\ldots,m\}. Each block is a semantically coherent unit whose textual realisation can be varied independently of the others.

Definition 2 (Block Variant Sets). For each block i∈[m]i \in[m], the variant set Vi\mathcal{V}_{i} is a finite non-empty set of admissible textual variants; the initial prompt contributes a distinguished vi(0)∈Viv_{i}^{(0)} \in\mathcal{V}_{i}, so that the initial prompt itself is always feasible.

Definition 3 (Block Mutability). Let Imut:={i:∣Vi∣≥2}I_{\mathrm{mut}} := \{i : |V_i| \ge2\} and Iimm:=[m]∖ImutI_{\mathrm{imm}} := [m] \setminus I_{\mathrm{mut}} be the mutable and immutable block sets. A block i∈Iimmi \in I_{\mathrm{imm}} has Vi={vi(0)}V_i = \{v_i^{(0)}\} and cannot be edited: it encodes a contract (safety clause, tool schema, output format) preserved verbatim throughout optimisation.

Definition 4 (Block Orderings). The ordering family Π⊆Sm\Pi\subseteq S_m is a finite family of admissible permutations over [m][m], with distinguished π(0)∈Π\pi^{(0)} \in\Pi corresponding to the initial layout.

Definition 5 (Prompt State and Search Space). A prompt state is a tuple x=(v1,…,vm,π)x = (v_1, \ldots, v_m, \pi) with vi∈Viv_i \in V_i and π∈Π\pi\in\Pi. The search space and initial state are

X=(∏i=1mVi)×Π,∣X∣=∣Π∣⋅∏i=1m∣Vi∣,x(0)=(v1(0),…,vm(0),π(0)).(1)\mathcal{X} = \left(\prod_{i=1}^{m} V_i\right) \times\Pi,\qquad|\mathcal{X}| = |\Pi| \cdot\prod_{i=1}^{m} |V_i|,\qquad x^{(0)} = (v_1^{(0)}, \ldots, v_m^{(0)}, \pi^{(0)}). \tag*{(1)}

X\mathcal{X} is finite but combinatorially large: ∣X∣|\mathcal{X}| quickly exceeds any realistic evaluation budget.

Definition 6 (Render Function). The rendering function render⁡:X→Σ∗\operatorname{render} : \mathcal{X} \to\Sigma^* maps a prompt state to a string over alphabet Σ\Sigma (typically Unicode) by concatenating vπ(1),…,vπ(m)v_{\pi(1)}, \ldots, v_{\pi(m)} in the order prescribed by π\pi with fixed template separators. It is deterministic and fixed throughout optimisation.

Combinatorial Objective

Definition 7 (System Agent). The system agent is a (possibly stochastic) LLM M(⋅ ;p):I→YM(\cdot\,; p) : \mathcal{I} \to\mathcal{Y} with p∈Σ∗p \in\Sigma^*, accessed strictly as a black box (no gradients, logits, or internal states).

Definition 8 (Bounded Reward). Reward is a bounded function r:Y×Y→[0,1]r : \mathcal{Y} \times\mathcal{Y} \to[0, 1]; canonical instantiations include 0/1 exact match, accuracy, F1F_1, rubric scores, or rescaled learned-judge outputs.

Definition 9 (Population Utility). The population utility of x∈Xx \in\mathcal{X} is the expected reward under P\mathcal{P},

F∗(x):=E(x,y)∼P[r(M(x;render⁡(x)),y)].(2)F^*(x) := \mathbb{E}_{(x,y)\sim\mathcal{P}}\left[r\left(M(x;\operatorname{render}(x)), y\right)\right]. \tag*{(2)}

with expectation over the random example and any stochasticity in MM.

Because F∗F^* is inaccessible, the search observes it only through an empirical surrogate:

Definition 10 (Empirical Utility). For x∈Xx \in\mathcal{X} and batch B⊆DB \subseteq\mathcal{D},

F(x;B):=1∣B∣∑(x,y)∈Br(M(x;render⁡(x)),y);(3)F(x; B) := \frac{1}{|B|}\sum_{(x,y)\in B} r\left(M(x;\operatorname{render}(x)), y\right); \tag*{(3)}

each oracle call consumes ∣B∣|B| model evaluations, and we write F(x):=F(x;D)F(x) := F(x; \mathcal{D}). The gap between F∗F^* (what we optimise) and FF (what we observe) is the source of the finite-sample bounds in Section E.

Selective Mutability as a Feasibility Constraint

Definition 3 makes contract preservation a constraint on the feasible set rather than an instruction to the proposer. Each named section of the prompt (role, objective, examples, constraints, tool schema, output format) is tagged mutable/immutable, and ∣Vi∣=1|V_i| = 1 makes every edit to an immutable block unreachable. Freezing shrinks the effective space by ∏i∈Iimm∣Vi∣\prod_{i\in I_{\mathrm{imm}}}|V_i|, the variants the frozen blocks would otherwise admit, and guarantees the contract’s text (safety, format, schema) by construction.

Length Regularisation as a Soft Penalty

Longer prompts add latency and cost to every call, and without a penalty prompts keep growing, since the proposer mostly adds text. We penalize growth rather than forbid it, using a ratio-based cost

κlen(x):=max⁡(0,len⁡(render⁡(x))len⁡(render⁡(x(0)))−1).(4)\kappa_{\mathrm{len}}(x) := \max\left(0, \frac{\operatorname{len}(\operatorname{render}(x))}{\operatorname{len}(\operatorname{render}(x^{(0)}))} - 1\right). \tag*{(4)}

The Constrained Problem

Definition 11 (Constrained Natural Language Optimization). Given mutability tags (Definition 3), a cost κ≥0\kappa\ge0 with κ(x(0))=0\kappa(x^{(0)}) = 0, and a weight λ>0\lambda> 0, solve

xλ⋆∈arg⁡max⁡x∈X Fλ(x),Fλ(x):=F∗(x)−λ⋅κ(x).(5)x_\lambda^\star\in\underset{x\in\mathcal{X}}{\arg\max}\ F^\lambda(x),\qquad F^\lambda(x) := F^*(x) - \lambda\cdot\kappa(x). \tag*{(5)}

Setting λ=0\lambda= 0 and declaring every block mutable recovers the unconstrained problem over the all-mutable space Xall\mathcal{X}_{\mathrm{all}}, with optimum xall∗x^*_{\mathrm{all}}, which most prior methods solve implicitly on a single string.

Optimization is a Walk over an Edit Graph

Problem (5) is combinatorial and FF is noisy, so any practical algorithm restricts to local moves sampled by a proposer and filtered by a selector. Prior NLO methods (APE, OPRO, ProTeGi, MAPO, MPO) and SPLICE all fit a single template, differing only in the state space they expose, the signal the proposer consumes, and how the selector retains candidates between rounds.

Definition 12 (Edit Graph). A primitive edit is either a block replacement vi→vi′∈Vi∖{vi}v_i \to v_i' \in\mathcal{V}_i \setminus\{v_i\} or an admissible reordering π→π′∈Π\pi\to\pi' \in\Pi; each produces a state x′∈Xx' \in\mathcal{X} differing from xx in exactly one coordinate. The edit graph G=(X,E)\mathcal{G} = (\mathcal{X}, E) has radius-one neighbourhood N(x)={x′:x′\mathcal{N}(x) = \{x' : x' is reachable from xx by one primitive edit}$.

Replacement and reordering act on disjoint coordinates, so they commute, giving diam⁡(G)≤mmut+diam⁡(Π)\operatorname{diam}(\mathcal{G}) \le m_{\mathrm{mut}} + \operatorname{diam}(\Pi) with mmut=∣Imut∣m_{\mathrm{mut}} = |I_{\mathrm{mut}}| (Proposition 3).

Definition 13 (Proposal Distribution). A proposal distribution is a conditional family qϕ(u∣x,Ht)q_{\phi}(u \mid x, H_t) over primitive edits, supported on edits that produce a feasible state x′=Apply⁡(x,u)∈Xx' = \operatorname{Apply}(x,u) \in\mathcal{X}, where the search history HtH_t holds every candidate evaluated before step tt with its parent, lineage and score, and the parents’ critiques at every step s≤ts \le t (step-tt ones computed before any step-tt proposal is drawn). In SPLICE and every baseline, qϕq_{\phi} is realised by an LLM conditioned on a textual encoding of (x,Ht)(x,H_t).

Feasibility is enforced by rejecting malformed generations (Assumption 2).

References

  1. [1]L. A. Agrawal, S. Tan, D. Soylu, N. Ziems, R. Khare, K. Opsahl-Ong, A. Singhvi, H. Shandilya, M. J. Ryan, M. Jiang, C. Potts, K. Sen, A. Dimakis, I. Stoica, D. Klein, M. Zaharia, and O. Khattab. GEPA: Reflective prompt evolution can outperform reinforcement learning. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=RQm2KQTM5r.arxiv.org/abs/2507.19457
  2. [2]J.-Y. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi-armed bandits. In Conference on Learning Theory (COLT), 2010.
  3. [3]D. Austin and E. Chartock. GRAD-SUM: Leveraging gradient summarization for optimal prompt engineering. arXiv preprint arXiv:2407.12865, 2024.arxiv.org/abs/2407.12865
  4. [4]M. Balunović, J. Dekoninck, I. Petrov, N. Jovanović, and M. Vechev. MathArena: Evaluating LLMs on uncontaminated math competitions. arXiv preprint arXiv:2505.23281, 2025.arxiv.org/abs/2505.23281
  5. [5]J. Bergstra and Y. Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13:281–305, 2012.
  6. [6]J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl. Algorithms for hyper-parameter optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2011.
  7. [7]A. Blum and M. Hardt. The ladder: A reliable leaderboard for machine learning competitions. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 1006–1014, 2015.
  8. [8]B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V. Le, C. Ré, and A. Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024.arxiv.org/abs/2407.21787
  9. [9]T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), 2020.arxiv.org/abs/2005.14165
  10. [10]L. Chen, M. Feldman, and A. Karbasi. Weakly submodular maximization beyond cardinality constraints: Does randomization help greedy? In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS), 2018.arxiv.org/abs/1707.04347
  11. [11]C.-A. Cheng, A. Nie, and A. Swaminathan. Trace is the next AutoDiff: Generative optimization with rich feedback, execution traces, and LLMs. In Advances in Neural Information Processing Systems (NeurIPS), 2024.arxiv.org/abs/2406.16218
  12. [12]J. Cheng, X. Liu, K. Zheng, P. Ke, H. Wang, Y. Dong, J. Tang, and M. Huang. Black-box prompt optimization: Aligning large language models without model training. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (ACL), 2024. URL https://arxiv.org/abs/2311.04155.
  13. [13]P. Clark, I. Cowhey, O. Etzioni, T. Khot, A. Sabharwal, C. Schoenick, and O. Tafjord. Think you have solved question answering? Try ARC, the AI2 reasoning challenge. arXiv preprint arXiv:1803.05457, 2018.arxiv.org/abs/1803.05457
  14. [14]K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.arxiv.org/abs/2110.14168
  15. [15]A. Cui, P. Nandylam, A. Rufail, E. Cheung, A. Lei, K. Zhu, and S. O’Brien. Introducing MAPO: Momentum-aided gradient descent prompt optimization. arXiv preprint arXiv:2410.19499, 2024.arxiv.org/abs/2410.19499
  16. [16]A. Das and D. Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on Machine Learning (ICML), 2011.arxiv.org/abs/1102.3975
  17. [17]M. Davari, U. Garg, W. Cai, and E. Belilovsky. Stabilizing black-box prompt optimization with textual regularization and signal aggregation, 2025. URL https://arxiv.org/abs/2507.09839.
  18. [18]K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002.DOI
  19. [19]M. Deng, J. Wang, C.-P. Hsieh, Y. Wang, H. Guo, T. Shu, M. Song, E. P. Xing, and Z. Hu. RLPrompt: Optimizing discrete text prompts with reinforcement learning. In Empirical Methods in Natural Language Processing (EMNLP), 2022.arxiv.org/abs/2205.12548
  20. [20]V. Y. Dong, R. Pryzant, Y. Liu, and J. Jiao. CAPO: Constraint-aware prompt optimization for LLM agents, 2026. URL https://arxiv.org/abs/2608.16068.
  21. [21]S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276(1–2):51–81, 2002.
  22. [22]C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC), pages 117–126, 2015.arxiv.org/abs/1411.2664
  23. [23]T. Elsken, J. H. Metzen, and F. Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20(55):1–21, 2019.arxiv.org/abs/1808.05377
  24. [24]E. Even-Dar, S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7:1079–1105, 2006.DOI
  25. [25]C. Fernando, D. S. Banarse, H. Michalewski, S. Osindero, and T. Rocktäschel. Promptbreeder: Self-referential self-improvement via prompt evolution. In International Conference on Machine Learning, pages 13481–13544. PMLR, 2024.arxiv.org/abs/2309.16797
  26. [26]F. Glover. Tabu search — Part I. ORSA Journal on Computing, 1(3):190–206, 1989.DOI
  27. [27]D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In International Conference on Genetic Algorithms (ICGA), pages 41–49, 1987.
  28. [28]Q. Guo, R. Wang, J. Guo, B. Li, K. Song, X. Tan, G. Liu, J. Bian, and Y. Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint arXiv:2309.08532, 2023.arxiv.org/abs/2309.08532
  29. [29]Y. Han, Y. Han, S. Huang, G. Liu, Z. Zhou, B. Liu, Y. Zhang, I. N. Shi, L. He, and T. Shi. MAPGD: Multi-agent prompt gradient descent for collaborative prompt optimization, 2025. URL https://arxiv.org/abs/2509.11361.
  30. [30]K. Helsgaun. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106–130, 2000.DOI
  31. [31]J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
  32. [32]O. Honovich, U. Shaham, S. R. Bowman, and O. Levy. Instruction induction: From few examples to natural language task descriptions. In Annual Meeting of the Association for Computational Linguistics (ACL), 2023.
  33. [33]H. H. Hoos and T. Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004.
  34. [34]S. Hu, C. Lu, and J. Clune. Automated design of agentic systems. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2408.08435
  35. [35]X. Hu, P. Tang, S. Zuo, Z. Wang, B. Song, Q. Lou, J. Jiao, and D. Charles. Evoke: Evoking critical thinking abilities in LLMs via reviewer-author prompt editing. arXiv preprint arXiv:2310.13855, 2023.arxiv.org/abs/2310.13855
  36. [36]F. Hutter, H. H. Hoos, and K. Leyton-Brown. Sequential model-based optimization for general algorithm configuration. In International Conference on Learning and Intelligent Optimization (LION), pages 507–523, 2011.DOI
  37. [37]G. Juneja, G. Jajoo, H. Li, J. Jiao, N. Natarajan, and A. Sharma. Task facet learning: A structured approach to prompt optimization. In Findings of the Association for Computational Linguistics: ACL 2025, pages 23473–23496, 2025.
  38. [38]E. K. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17(1):1–42, 2016.
  39. [39]O. Khattab, A. Singhvi, P. Maheshwari, Z. Zhang, K. Santhanam, S. Haq, A. Sharma, T. T. Joshi, H. Moazam, H. Miller, et al. DSPy: Compiling declarative language model calls into state-of-the-art pipelines. In The Twelfth International Conference on Learning Representations, 2024.
  40. [40]S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983.
  41. [42]N. Kulin, V. Zhuravlev, A. Khairullin, S. Muravyov, I. Makarov, D. Sukhorukov, and E. Averkova. From monolithic to modular: Segment-level automatic prompt optimization. In IJCAI-ECAI Workshop on Robustifying Generative AI (RobustifAI), 2026. URL https://arxiv.org/abs/2608.11219.
  42. [43]J. Lehman and K. O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation, 19(2):189–223, 2011.DOI
  43. [45]D. Li, C. Shi, W. Ou, C. Shen, and J. Yang. Efficient multi-objective prompt optimization via pure-exploration bandits. In International Conference on Learning Representations (ICLR), 2026. URL https://arxiv.org/abs/2605.14553.
  44. [47]A. Lieander, J. H. Wang, and K. Rafferty. Prompt optimization with two gradients for classification in large language models. AI, 6(8):182, 2025.DOI
  45. [48]S. Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10):2245–2269, 1965.DOI
  46. [49]S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2):498–516, 1973.DOI
  47. [50]H. Liu, K. Simonyan, and Y. Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019.arxiv.org/abs/1806.09055
  48. [51]P. Liu, W. Yuan, J. Fu, Z. Jiang, H. Hayashi, and G. Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9), 2023.arxiv.org/abs/2107.13586
  49. [52]B. T. Lowerre. The HARPY Speech Recognition System. PhD thesis, Carnegie Mellon University, 1976.
  50. [53]P. Lu, Z. Hong, Z. Shang, Z. Wang, Y. Ban, Y. Shu, M. Zhang, S. Qiu, and Z. Dai. FedPOB: Sample-efficient federated prompt optimization via bandits, 2025. URL https://arxiv.org/abs/2509.24701.
  51. [54]Y. Lu, M. Bartolo, A. Moore, S. Riedel, and P. Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Annual Meeting of the Association for Computational Linguistics (ACL), 2022.arxiv.org/abs/2104.08786
  52. [55]A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegrefe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, S. Welleck, B. P. Majumder, S. Gupta, A. Yazdanbakhsh, and P. Clark. Self-Refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2303.17651
  53. [57]G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1):265–294, 1978.DOI
  54. [58]J. Nian, Z. Peng, H. Shang, D. H. Park, and Y. Fang. Submodular evaluation subset selection in automatic prompt optimization, 2026. URL https://arxiv.org/abs/2601.03493.
  55. [59]A. Novikov, N. Vũ, M. Eisenberger, E. Dupont, P.-S. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. R. Ruiz, A. Mehrabian, M. P. Kumar, A. See, S. Chaudhuri, G. Holland, A. Davies, S. Nowozin, P. Kohli, and M. Balog. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131, 2025.
  56. [60]K. Opsahl-Ong, M. J. Ryan, J. Purtell, D. Broman, C. Potts, M. Zaharia, and O. Khattab. Optimizing instructions and demonstrations for multi-stage language model programs. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 9340–9366, 2024.
  57. [61]A. Prasad, P. Hase, X. Zhou, and M. Bansal. GrIPS: Gradient-free, edit-based instruction search for prompting large language models. In European Chapter of the Association for Computational Linguistics (EACL), 2023.
  58. [62]R. Pryzant, D. Iter, J. Li, Y. Lee, C. Zhu, and M. Zeng. Automatic prompt optimization with “gradient descent” and beam search. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 7957–7968, 2023.
  59. [63]E. Real, A. Aggarwal, Y. Huang, and O. V. Le. Regularized evolution for image classifier architecture search. In AAAI Conference on Artificial Intelligence, 2019.
  60. [64]D. Rein, B. L. Hou, A. C. Stickland, J. Petty, R. Y. Pang, J. Dirani, J. Michael, and S. R. Bowman. GPQA: A graduate-level Google-proof Q&A benchmark. In First Conference on Language Modeling (COLM), 2024.arxiv.org/abs/2311.12022
  61. [65]R. Rishav, P. Pujari, and P. Rastogi. ContraPrompt: Contrastive prompt optimization via dyadic reasoning trace analysis. In ICLR 2026 Workshop on Logical Reasoning of Large Language Models, 2026. URL https://openreview.net/forum?id=86E9P53xbM.
  62. [66]B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, Q. Fawzi, P. Kohli, and A. Fawzi. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, 2024.
  63. [67]D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1232–1240, 2016.
  64. [68]J. Schmidhuber. Goedel machines: Self-referential universal problem solvers making provably optimal self-improvements. arXiv preprint arXiv:cs/0309048, 2003.
  65. [69]X. Sécheresse, J.-Y. Guilbert-Ly, and A. Villedieu de Torcy. GAAPO: Genetic algorithmic applied to prompt optimization. arXiv preprint arXiv:2504.07157, 2025.
  66. [70]P. Sharma and A. Z. Henley. Modular prompt optimization: Optimizing structured prompts with section-local textual gradients. arXiv preprint arXiv:2601.04055, 2026.arxiv.org/abs/2601.04055
  67. [71]T. Shin, Y. Razeghi, R. L. Logan IV, E. Wallace, and S. Singh. AutoPrompt: Eliciting knowledge from language models with automatically generated prompts. In Empirical Methods in Natural Language Processing (EMNLP), 2020.arxiv.org/abs/2010.15980
  68. [72]N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2303.11366
  69. [73]L. Siyan, V. C. Raghuram, O. Khattab, J. Hirschberg, and Z. Yu. PAPILLON: Privacy preservation from Internet-based and local language model ensembles. In L. Chiruzzo, A. Ritter, and L. Wang, editors, Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 3371–3390, Albuquerque, New Mexico, Apr. 2025. Association for Computational Linguistics. ISBN 979-8-89176-189-6. doi: 10.18653/v1/2025.naacl-long.173. URL https://aclanthology.org/2025.naacl-long.173/.
  70. [74]C. Snell, J. Lee, K. Xu, and A. Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2408.03314
  71. [75]R. Socher, A. Perelygin, J. Wu, J. Chuang, C. D. Manning, A. Y. Ng, and C. Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631–1642, 2013.DOI
  72. [76]M. Suzgun, N. Scales, N. Schärli, S. Gehrmann, Y. Tay, H. W. Chung, A. Chowdhery, Q. Le, E. Chi, D. Zhou, and J. Wei. Challenging BIG-Bench tasks and whether chain-of-thought can solve them. In Findings of the Association for Computational Linguistics: ACL 2023, pages 13003–13051. Association for Computational Linguistics, 2023.arxiv.org/abs/2210.09261
  73. [77]X. Wang and T. Wang. FOZO: Forward-only zeroth-order prompt optimization for test-time adaptation. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2026. URL https://arxiv.org/abs/2603.04733.
  74. [78]X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representations (ICLR), 2023.arxiv.org/abs/2203.11171
  75. [79]X. Wang, C. Li, Z. Wang, F. Bai, H. Luo, J. Zhang, N. Jojic, E. P. Xing, and Z. Hu. PromptAgent: Strategic planning with language models enables expert-level prompt optimization. In International Conference on Learning Representations (ICLR), 2024.arxiv.org/abs/2310.16427
  76. [80]Z. Wang, Y. Dong, O. Delalleau, J. Zeng, G. Shen, D. Egert, J. J. Zhang, M. N. Sreedhar, and O. Kuchaiev. HelpSteer2: Open-source dataset for training top-performing reward models. Advances in Neural Information Processing Systems, 37:1474–1501, 2024.arxiv.org/abs/2406.08673
  77. [81]J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems (NeurIPS), 2022.arxiv.org/abs/2201.11903
  78. [82]Y. Wu, Y. Gao, B. B. Zhu, Z. Zhou, X. Sun, S. Yang, J.-G. Lou, Z. Ding, and L. Yang. StraGo: Harnessing strategic guidance for prompt optimization, 2024. URL https://arxiv.org/abs/2410.08601.
  79. [83]C. Yang, X. Wang, Y. Lu, H. Liu, Q. V. Le, D. Zhou, and X. Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=Bb4VG0WELI.arxiv.org/abs/2309.03409
  80. [84]S. Yao, D. Yu, J. Zhao, I. Shafran, T. L. Griffiths, Y. Cao, and K. Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2305.10601
  81. [85]L. Yin and Z. Wang. LLM-AutoDiff: Auto-differentiate any LLM workflow. arXiv preprint arXiv:2501.16673, 2025.arxiv.org/abs/2501.16673
  82. [86]X. Yin, X. Wang, L. Pan, L. Lin, X. Wan, and W. Y. Wang. Gödel Agent: A self-referential agent framework for recursive self-improvement. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), 2025. arXiv:2410.04444.arxiv.org/abs/2410.04444
  83. [87]M. Yuksekgonul, F. Bianchi, J. Boen, S. Liu, Z. Huang, C. Guestrin, and J. Zou. TextGrad: Automatic “differentiation” via text. arXiv preprint arXiv:2406.07496, 2024.arxiv.org/abs/2406.07496
  84. [88]T. Zehle, M. Schlager, T. Heiß, and M. Feurer. CAPO: Cost-aware prompt optimization. In Proceedings of the Fourth International Conference on Automated Machine Learning, volume 293 of Proceedings of Machine Learning Research, pages 18/1–45. PMLR, 2025.arxiv.org/abs/2504.16005
  85. [89]T. Zehle, T. Heiß, M. Schlager, M. Aßenmacher, and M. Feurer. promptolution: A unified, modular framework for prompt optimization. In Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 3: System Demonstrations), pages 282–296, 2026.
  86. [90]E. Zelikman, E. Lorch, L. Mackey, and A. T. Kalai. Self-taught optimizer (STOP): Recursively self-improving code generation. In Conference on Language Modeling (COLM), 2024. arXiv:2310.02304.arxiv.org/abs/2310.02304
  87. [91]J. Zhang, S. Hu, C. Lu, R. Lange, and J. Clune. Darwin Gödel machine: Open-ended evolution of self-improving agents. arXiv preprint arXiv:2505.22954, 2025.arxiv.org/abs/2505.22954
  88. [92]J. Zhang, J. Xiang, Z. Yu, F. Teng, X. Chen, J. Chen, M. Zhuge, X. Cheng, S. Hong, J. Wang, B. Zheng, B. Liu, Y. Luo, and C. Wu. AFlow: Automating agentic workflow generation. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2410.10762
  89. [93]Y. Zhou, A. I. Muresanu, Z. Han, K. Paster, S. Pitis, H. Chan, and J. Ba. Large language models are human-level prompt engineers. In The Eleventh International Conference on Learning Representations, 2023.arxiv.org/abs/2211.01910
  90. [94]Z. Zhou, Y. Wu, J. Yang, Z. Xiao, and R. Li. Evaluating the effectiveness of black-box prompt optimization as the scale of LLMs continues to grow. arXiv preprint arXiv:2505.08303, 2025.arxiv.org/abs/2505.08303
  91. [95]B. Zoph and Q. V. Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations (ICLR), 2017.arxiv.org/abs/1611.01578

Paper details

vlnc:W_95d4evtr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents