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 ∼ 3 × 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 = ( v 1 , … , v m , π ) x=(v_1,\ldots,v_m,\pi) x = ( v 1 , … , v m , π ) ; 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).
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} 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 k k k edits to mutable blocks, scores children on D v a l i d D_{\mathrm{valid}} D 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.
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 n r e n_{\mathrm{re}} n re fresh examples each step, the beam’s best score regresses by more than ε \varepsilon ε with probability at most W ( 1 + k ) exp ( − n r e ε 2 / c σ ) W(1+k)\exp(-n_{\mathrm{re}}\varepsilon^2/c_{\sigma}) W ( 1 + k ) exp ( − n re ε 2 / c σ ) , for a constant c σ ≤ 2 c_{\sigma} \le2 c σ ≤ 2 (Theorem 2 and Corollary 1). Assuming in addition a proposer whose edits improve with probability at least p ⋆ p^{\star} p ⋆ 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 ⋆ ) W k 1-(1-p^{\star})^{Wk} 1 − ( 1 − p ⋆ ) W k (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} γ − 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}) λ ⋅ κ ( x ⋆ ) (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-N N N by +1.2–1.7 pp, and Elitist Beam leads the best plain Best-of-N N N 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} I with unknown distribution P \mathcal{P} 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 ∼ P N \mathcal{D} \sim\mathcal{P}^{N} D ∼ P N to score candidates; a disjoint D v a l i d \mathcal{D}_{\mathrm{valid}} D valid scores candidates for selection (the proposer never sees its examples), and D t e s t \mathcal{D}_{\mathrm{test}} D 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} P within a finite evaluation budget.
Definition 1 (Prompt Template). A prompt consists of m ≥ 1 m \ge1 m ≥ 1 blocks, indexed by [ m ] = { 1 , … , m } [m] = \{1,\ldots,m\} [ m ] = { 1 , … , 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] i ∈ [ m ] , the variant set V i \mathcal{V}_{i} V i is a finite non-empty set of admissible textual variants; the initial prompt contributes a distinguished v i ( 0 ) ∈ V i v_{i}^{(0)} \in\mathcal{V}_{i} v i ( 0 ) ∈ V i , so that the initial prompt itself is always feasible.
Definition 3 (Block Mutability). Let I m u t : = { i : ∣ V i ∣ ≥ 2 } I_{\mathrm{mut}} := \{i : |V_i| \ge2\} I mut := { i : ∣ V i ∣ ≥ 2 } and I i m m : = [ m ] ∖ I m u t I_{\mathrm{imm}} := [m] \setminus I_{\mathrm{mut}} I imm := [ m ] ∖ I mut be the mutable and immutable block sets. A block i ∈ I i m m i \in I_{\mathrm{imm}} i ∈ I imm has V i = { v i ( 0 ) } V_i = \{v_i^{(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 Π ⊆ S m \Pi\subseteq S_m Π ⊆ S m is a finite family of admissible permutations over [ m ] [m] [ m ] , with distinguished π ( 0 ) ∈ Π \pi^{(0)} \in\Pi π ( 0 ) ∈ Π corresponding to the initial layout.
Definition 5 (Prompt State and Search Space). A prompt state is a tuple x = ( v 1 , … , v m , π ) x = (v_1, \ldots, v_m, \pi) x = ( v 1 , … , v m , π ) with v i ∈ V i v_i \in V_i v i ∈ V i and π ∈ Π \pi\in\Pi π ∈ Π . The search space and initial state are
X = ( ∏ i = 1 m V i ) × Π , ∣ X ∣ = ∣ Π ∣ ⋅ ∏ i = 1 m ∣ V i ∣ , x ( 0 ) = ( v 1 ( 0 ) , … , v m ( 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 = ( i = 1 ∏ m V i ) × Π , ∣ X ∣ = ∣Π∣ ⋅ i = 1 ∏ m ∣ V i ∣ , x ( 0 ) = ( v 1 ( 0 ) , … , v m ( 0 ) , π ( 0 ) ) . (1)
X \mathcal{X} X is finite but combinatorially large: ∣ X ∣ |\mathcal{X}| ∣ X ∣ quickly exceeds any realistic evaluation budget.
Definition 6 (Render Function). The rendering function render : X → Σ ∗ \operatorname{render} : \mathcal{X} \to\Sigma^* render : X → Σ ∗ 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)} v π ( 1 ) , … , v π ( 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 → Y M(\cdot\,; p) : \mathcal{I} \to\mathcal{Y} M ( ⋅ ; p ) : I → Y with p ∈ Σ ∗ p \in\Sigma^* p ∈ Σ ∗ , 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] r : Y × Y → [ 0 , 1 ] ; canonical instantiations include 0/1 exact match, accuracy, F 1 F_1 F 1 , rubric scores, or rescaled learned-judge outputs.
Definition 9 (Population Utility). The population utility of x ∈ X x \in\mathcal{X} x ∈ X is the expected reward under P \mathcal{P} 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)} F ∗ ( x ) := E ( x , y ) ∼ P [ r ( M ( x ; render ( x )) , y ) ] . (2)
with expectation over the random example and any stochasticity in M M M .
Because F ∗ F^* F ∗ is inaccessible, the search observes it only through an empirical surrogate:
Definition 10 (Empirical Utility). For x ∈ X x \in\mathcal{X} x ∈ X and batch B ⊆ D B \subseteq\mathcal{D} B ⊆ D ,
F ( x ; B ) : = 1 ∣ B ∣ ∑ ( x , y ) ∈ B r ( 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)} F ( x ; B ) := ∣ B ∣ 1 ( x , y ) ∈ B ∑ r ( M ( x ; render ( x )) , y ) ; (3)
each oracle call consumes ∣ B ∣ |B| ∣ B ∣ model evaluations, and we write F ( x ) : = F ( x ; D ) F(x) := F(x; \mathcal{D}) F ( x ) := F ( x ; D ) . The gap between F ∗ F^* F ∗ (what we optimise) and F F F (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 ∣ V i ∣ = 1 |V_i| = 1 ∣ V i ∣ = 1 makes every edit to an immutable block unreachable. Freezing shrinks the effective space by ∏ i ∈ I i m m ∣ V i ∣ \prod_{i\in I_{\mathrm{imm}}}|V_i| ∏ i ∈ I 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
κ l e n ( 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)} κ len ( x ) := max ( 0 , len ( render ( x ( 0 ) )) len ( render ( x )) − 1 ) . (4)
The Constrained Problem
Definition 11 (Constrained Natural Language Optimization). Given mutability tags (Definition 3), a cost κ ≥ 0 \kappa\ge0 κ ≥ 0 with κ ( x ( 0 ) ) = 0 \kappa(x^{(0)}) = 0 κ ( x ( 0 ) ) = 0 , and a weight λ > 0 \lambda> 0 λ > 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)} x λ ⋆ ∈ x ∈ X arg max F λ ( x ) , F λ ( x ) := F ∗ ( x ) − λ ⋅ κ ( x ) . (5)
Setting λ = 0 \lambda= 0 λ = 0 and declaring every block mutable recovers the unconstrained problem over the all-mutable space X a l l \mathcal{X}_{\mathrm{all}} X all , with optimum x a l l ∗ x^*_{\mathrm{all}} x all ∗ , which most prior methods solve implicitly on a single string.
Optimization is a Walk over an Edit Graph
Problem (5) is combinatorial and F F F 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 v i → v i ′ ∈ V i ∖ { v i } v_i \to v_i' \in\mathcal{V}_i \setminus\{v_i\} v i → v i ′ ∈ V i ∖ { v i } or an admissible reordering π → π ′ ∈ Π \pi\to\pi' \in\Pi π → π ′ ∈ Π ; each produces a state x ′ ∈ X x' \in\mathcal{X} x ′ ∈ X differing from x x x in exactly one coordinate. The edit graph G = ( X , E ) \mathcal{G} = (\mathcal{X}, E) G = ( X , E ) has radius-one neighbourhood N ( x ) = { x ′ : x ′ \mathcal{N}(x) = \{x' : x' N ( x ) = { x ′ : x ′ is reachable from x x x by one primitive edit}$.
Replacement and reordering act on disjoint coordinates, so they commute, giving diam ( G ) ≤ m m u t + diam ( Π ) \operatorname{diam}(\mathcal{G}) \le m_{\mathrm{mut}} + \operatorname{diam}(\Pi) diam ( G ) ≤ m mut + diam ( Π ) with m m u t = ∣ I m u t ∣ m_{\mathrm{mut}} = |I_{\mathrm{mut}}| m mut = ∣ I mut ∣ (Proposition 3).
Definition 13 (Proposal Distribution). A proposal distribution is a conditional family q ϕ ( u ∣ x , H t ) q_{\phi}(u \mid x, H_t) q ϕ ( u ∣ x , H t ) over primitive edits, supported on edits that produce a feasible state x ′ = Apply ( x , u ) ∈ X x' = \operatorname{Apply}(x,u) \in\mathcal{X} x ′ = Apply ( x , u ) ∈ X , where the search history H t H_t H t holds every candidate evaluated before step t t t with its parent, lineage and score, and the parents’ critiques at every step s ≤ t s \le t s ≤ t (step-t t t ones computed before any step-t t t proposal is drawn). In SPLICE and every baseline, q ϕ q_{\phi} q ϕ is realised by an LLM conditioned on a textual encoding of ( x , H t ) (x,H_t) ( x , H t ) .
Feasibility is enforced by rejecting malformed generations (Assumption 2).
Definition 14 (Batched Iterative Prompt Search). Given q ϕ q_{\phi} q ϕ , beam width W ≥ 1 W \ge1 W ≥ 1 , per-parent fan-out k ≥ 1 k \ge1 k ≥ 1 , and selectors { S t } t ≥ 1 \{S_t\}_{t \ge1} { S t } t ≥ 1 , the iterates are
C t = S t ( F t ) , F t = C t − 1 ∪ ⋃ x ∈ C t − 1 { Apply ( x , u j ) : u j ∼ q ϕ ( ⋅ ∣ x , H t ) } j = 1 k (6) C_t = S_t(F_t), \qquad F_t = C_{t-1} \cup\bigcup_{x \in C_{t-1}} \{\operatorname{Apply}(x,u_j) : u_j \sim q_{\phi}(\cdot\mid x,H_t)\}_{j=1}^{k} \tag*{(6)} C t = S t ( F t ) , F t = C t − 1 ∪ x ∈ C t − 1 ⋃ { Apply ( x , u j ) : u j ∼ q ϕ ( ⋅ ∣ x , H t ) } j = 1 k (6) starting from C 0 = { x ( 0 ) } C_0 = \{x^{(0)}\} C 0 = { x ( 0 ) } , with S t : 2 X → 2 X S_t : 2^{\mathcal{X}} \to2^{\mathcal{X}} S t : 2 X → 2 X , ∣ S t ( F ) ∣ ≤ W |S_t(F)| \le W ∣ S t ( F ) ∣ ≤ W ; F t F_t F t is the frontier.
Greedy hill-climbing, beam search, and elitist beam search recover as specific selectors S t S_t S t on the monolithic state space; Table 1 records where each prior method sits along the design axes (state space, gradient signal, selector and constraints) that together determine an algorithm (all methods: Table 5). Methods outside the template, such as GEPA and MIPROv2, depart from it in named components (Section C, Figure 6). SPLICE’s contribution is the particular combination of these axes, which we now describe.
SPLICE realises Definition 14 as a loop (Algorithm 1, Section D). At step t t t it re-scores the beam C t − 1 C_{t-1} C t − 1 on a training batch B t B_t B t and obtains section-local dual gradients from a critique agent; builds a momentum context from the gradient history G t − 1 G_{t-1} G t − 1 ; samples k k k edits per parent from q ϕ q_{\phi} q ϕ restricted to mutable blocks ; scores the children N t N_t N t on D v a l i d D_{\mathrm{valid}} D valid with F ~ ( x ) = F ( x ; D v a l i d ) − λ κ ( x ) \widetilde{F}(x) = F(x;D_{\mathrm{valid}}) - \lambda\kappa(x) F ( x ) = F ( x ; D valid ) − λκ ( x ) ; keeps W W W members of F t = C t − 1 ∪ N t F_t = C_{t-1} \cup N_t F t = C t − 1 ∪ N t with an elitist selector that reserves diversity slots; and records ( g t , Δ t ) (g_t,\Delta_t) ( g t , Δ t ) in G t G_t G t for the next step’s momentum. It returns the leader ( C T ) (C_T) ( C T ) , where leader( C ) = arg max x ∈ C F ~ ( x ) (C) = \operatorname*{arg\,max}_{x \in C} \widetilde{F}(x) ( C ) = arg max x ∈ C F ( x ) . Selective mutability and the length penalty (above) fix what is optimised; two independent design choices fill the loop’s steps, which we take in order.
Critique: Dual, Section-Local Gradients with Momentum
Critique output. The critique agent M c r i t M_{\mathrm{crit}} M crit consumes per-example traces on B t B_t B t and returns
Crit t ( x ) = ( n ( x ) , p ( x ) , { ( n i , p i ) } i ∈ I m u t , g ( x ) ) , (7) \operatorname{Crit}_t(x) = \left(\mathbf{n}(x), \mathbf{p}(x), \{(n_i,p_i)\}_{i \in I_{\mathrm{mut}}}, g(x)\right), \tag*{(7)} Crit t ( x ) = ( n ( x ) , p ( x ) , {( n i , p i ) } i ∈ I mut , g ( x ) ) , (7)
with failure-patterns n \mathbf{n} n , success-patterns p \mathbf{p} p , per-block assessments ( n i , p i ) (n_i,p_i) ( n i , p i ) , and a directional summary g ( x ) g(x) g ( x ) (“AWAY from X, TOWARD Y, PRESERVE Z”) playing the role of a gradient. Duality keeps the proposer from chasing batch failures while losing working content; section-localisation makes g ( x ) g(x) g ( x ) an addressable per-block update rather than a whole-prompt cue.
Textual momentum. Per-step batches make g t g_t g t noisy across steps, and natural-language gradients cannot be averaged vectorially. SPLICE instead surfaces the gradient trajectory
G t = { ( s , g s , Δ s ) } s ≤ t , Δ s : = F ~ ( leader ( C s ) ) − F ~ ( leader ( C s − 1 ) ) (8) G_t = \{(s,g_s,\Delta_s)\}_{s \le t}, \quad\Delta_s := \widetilde{F}(\operatorname{leader}(C_s))-\widetilde{F}(\operatorname{leader}(C_{s-1})) \tag*{(8)} G t = {( s , g s , Δ s ) } s ≤ t , Δ s := F ( leader ( C s )) − F ( leader ( C s − 1 )) (8)
exposing the last w w w entries (w = 5 w = 5 w = 5 ) to the proposer, so it can keep following a direction that has moved the leader. Since the leader never falls (Lemma 1), Δ s ≥ 0 \Delta_s \ge0 Δ s ≥ 0 : momentum records what helped.
Proposals and Reachability
The proposer is conditioned on ( render ( x ) , F ~ ( x ) , Crit t ( x ) , G t − 1 , I m u t ) \left(\operatorname{render}(x),\widetilde{F}(x),\operatorname{Crit}_t(x),G_{t-1},I_{\mathrm{mut}}\right) ( render ( x ) , F ( x ) , Crit t ( x ) , G t − 1 , I mut ) and samples k k k structurally-valid edits per parent at non-zero temperature. If the proposer is competent (Assumption 1), then while no beam member is ε \varepsilon ε -optimal the W k Wk W k children of a step contain an improving one with probability at least 1 − ( 1 − p ) W k 1-(1-p)^{Wk} 1 − ( 1 − p ) W k (Theorem 3), so beam width and fan-out trade off directly.
Selection: Elitism with Diversity Slots
Frontier elitism. The selector ranks parents and children symmetrically on F t = C t − 1 ∪ N t \mathcal{F}_t = C_{t-1} \cup\mathcal{N}_t F t = C t − 1 ∪ N t under the regularised validation score F ~ ( ⋅ ; D v a l i d ) \widetilde{F}(\cdot;D_{\mathrm{valid}}) F ( ⋅ ; D valid ) , computed at first evaluation and cached while a candidate stays in the beam (re-rolling would introduce selection-on-noise bias). The leader score ℓ t : = max x ∈ C t F ~ ( x ; D v a l i d ) \ell_t := \max_{x \in C_t}\widetilde{F}(x;D_{\mathrm{valid}}) ℓ t := max x ∈ C t F ( x ; D valid ) therefore never falls (Lemma 1); re-scoring instead would need large batches to control regression (Theorem 2).
Diversity slots. Each candidate carries id ( x ) \operatorname{id}(x) id ( x ) , a parent pointer, and an accumulated lineage ( x ) \operatorname{lineage}(x) lineage ( x ) . SPLICE reserves D ∈ { 0 , … , W − 1 } D \in\{0,\ldots,W-1\} D ∈ { 0 , … , W − 1 } beam slots for diversity, filled by PICKDIVERSE (Algorithm 3): scan the non-elite pool in score order, accept the first candidate clearing the quality gate τ t : = ϱ ⋅ ℓ t \tau_t := \varrho\cdot\ell_t τ t := ϱ ⋅ ℓ t under progressively weaker novelty (Tier 1: new lineage born this step; Tier 2: new lineage any generation; Tier 3: different immediate parent), and backfill empty slots. Every ancestor set contains the seed, so in practice Tier 3 operates: the beam keeps a competitive different-parent candidate when one exists (Theorem 1).
The gate, and the output rule. Monotone ℓ t \ell_t ℓ t (Lemma 1) and τ t = ϱ ℓ t \tau_t = \varrho\ell_t τ t = ϱ ℓ t give a non-decreasing gate when ϱ > 0 \varrho> 0 ϱ > 0 : a candidate whose cached score falls below τ t \tau_t τ t is ineligible for diversity selection thereafter (Proposition 1), which reads as annealing without a temperature (an interpretation, not a guarantee). SPLICE returns leader ( C T ) \operatorname{leader}(C_T) leader ( C T ) , whose validation score is biased upward as a maximum over the history (Theorem 7 ); the reported test score is free of it.
Each design choice is a column of Table 1; § 3 states the guarantees, and Sections D to E give the full solver, statements and proofs.
Theoretical Guarantees
An LLM-driven search does not admit end-to-end guarantees: the proposer is a model we do not control, scores are noisy, and the utility need not be submodular. We therefore state what holds at three levels of assumption: with no assumption on rewards or proposer; with bounded rewards and i.i.d. batches; and for the rate results only, with a competent proposer (assumptions per result: Table 6 ). Throughout, a candidate’s validation score is computed once and cached while it stays in the beam (reachability, convergence and the exclusion claim of Proposition 1 assume it cached per state ). Proofs are in Section E.
Table 6. Table 6: The results of Section E at a glance. Each row gives a result, what it says, and what it rests on. Proposal coverage, in its population form (Asm. 1) and its scored form (Asm. 5), is the assumption about the LLM proposer that we cannot verify; only the three rate results in the bottom block use it. The middle block rests on γ \gamma γ -submodularity (Asm. 4) instead, for which we have no per-benchmark estimator.
No Assumption on Rewards or Proposer
Lemma 1 (Leader monotonicity under cached scoring). Under cached scoring and the selector S e l i t - d i v \mathcal{S}_{\mathrm{elit\text{-}div}} S elit - div , the per-step leader score ℓ t : = max x ∈ C t F ~ ( x ; D v a l i d ) \ell_t := \max_{x \in C_t}\widetilde{F}(x;D_{\mathrm{valid}}) ℓ t := max x ∈ C t F ( x ; D valid ) is non-decreasing: ℓ t ≥ ℓ t − 1 ∀ t ≥ 1 \ell_t \ge\ell_{t-1}\ \forall t \ge1 ℓ t ≥ ℓ t − 1 ∀ t ≥ 1 .
It is a lemma, not a claim about search dynamics: it follows from the definitions for any elitist selector and any proposer, and the returned prompt therefore never scores below the seed on validation.
Theorem 1 (Diversity preservation). Let 1 ≤ D ≤ W − 1 1 \le D \le W-1 1 ≤ D ≤ W − 1 and ϱ ∈ [ 0 , 1 ] \varrho\in[0,1] ϱ ∈ [ 0 , 1 ] . If F t \mathcal{F}_t F t contains c ∗ c^* c ∗ with F ~ ( c ∗ ) ≥ ϱ ⋅ ℓ t \widetilde{F}(c^*) \ge\varrho\cdot\ell_t F ( c ∗ ) ≥ ϱ ⋅ ℓ t whose parent is not the parent of any elite, then C t C_t C t contains a member scoring at least ϱ ⋅ ℓ t \varrho\cdot\ell_t ϱ ⋅ ℓ t whose parent is not the parent of any elite.
Proposition 1 (Gate monotonicity). Under cached scoring and S e l i t - d i v \mathcal{S}_{\mathrm{elit\text{-}div}} S elit - div with ϱ > 0 \varrho> 0 ϱ > 0 , the quality floor τ t = ϱ ⋅ ℓ t \tau_t = \varrho\cdot\ell_t τ t = ϱ ⋅ ℓ t is non-decreasing in t t t , and, with scores cached per state, a candidate whose score falls below τ t \tau_t τ t is ineligible for diversity selection at every later step.
The diversity guarantee is conditional : the selector retains a competitive candidate of a different parent when one exists, and the proposer must generate it (lineage-level variant: Theorem 6 ).
Bounded Rewards: Noisy No-Regression
Caching is a choice. If instead every frontier member were re-scored on n r e n_{\mathrm{re}} n re fresh i.i.d. examples each step and selected on those unregularized scores (λ = 0 \lambda= 0 λ = 0 ), regression of the beam’s best population score f t ⋆ : = max x ∈ C t F ⋆ ( x ) f_t^\star:= \max_{x \in C_t} F^\star(x) f t ⋆ := max x ∈ C t F ⋆ ( x ) is controlled by the batch size:
Theorem 2 (Probabilistic no-regression under re-evaluation). With rewards in [ 0 , 1 ] [0,1] [ 0 , 1 ] and an elitist selector, for any ε > 0 \varepsilon> 0 ε > 0 , Pr [ f t ⋆ < f t − 1 ⋆ − ε ] ≤ ( ∣ F t ∣ − 1 ) exp ( − n r e ε 2 / c σ ) \Pr[f_t^\star< f_{t-1}^\star- \varepsilon] \le(|F_t| - 1)\exp(-n_{\mathrm{re}}\varepsilon^2/c_\sigma) Pr [ f t ⋆ < f t − 1 ⋆ − ε ] ≤ ( ∣ F t ∣ − 1 ) exp ( − n re ε 2 / c σ ) , where ∣ F t ∣ ≤ W ( 1 + k ) |F_t| \le W(1+k) ∣ F t ∣ ≤ W ( 1 + k ) , and c σ = 4 σ 2 ≤ 1 c_\sigma= 4\sigma^2 \le1 c σ = 4 σ 2 ≤ 1 for independent batches and c σ = 2 c_\sigma= 2 c σ = 2 for a shared batch.
Corollary 1 (Minimum batch size). Pr [ f t ⋆ < f t − 1 ⋆ − ε ] ≤ δ \Pr[f_t^\star< f_{t-1}^\star- \varepsilon] \le\delta Pr [ f t ⋆ < f t − 1 ⋆ − ε ] ≤ δ whenever n r e ≥ ( c σ / ε 2 ) log ( W ( 1 + k ) / δ ) n_{\mathrm{re}} \ge(c_\sigma/\varepsilon^2)\log(W(1+k)/\delta) n re ≥ ( c σ / ε 2 ) log ( W ( 1 + k ) / δ ) .
At W = 4 W=4 W = 4 , k = 3 k=3 k = 3 , δ = 0.05 \delta=0.05 δ = 0.05 and c σ = 1 c_\sigma=1 c σ = 1 this requires n r e ≥ 145 n_{\mathrm{re}} \ge145 n re ≥ 145 at ε = 0.2 \varepsilon= 0.2 ε = 0.2 , above most of our per-step batches, which is why SPLICE caches scores instead of re-scoring.
A Competent Proposer: Rates
The rate results need one assumption about the LLM proposer, which we cannot prove and instead measure through a proxy (Section F.4.1):
Assumption 1 (Proposal coverage on the ε \varepsilon ε -sublevel set). Fix a tolerance ε > 0 \varepsilon> 0 ε > 0 in advance. With u u u improving from x x x when F ~ ( Apply ( x , u ) ) > F ~ ( x ) \widetilde{F}(\operatorname{Apply}(x,u)) > \widetilde{F}(x) F ( Apply ( x , u )) > F ( x ) , let p ⋆ ( ε ) : = min x : max X F ⋆ − F ⋆ ( x ) ≥ ε Pr u ∼ q ϕ ( ⋅ ∣ x , H t ) [ u is improving from x ] p^\star(\varepsilon) := \min_{x:\max_{X}F^\star-F^\star(x)\ge\varepsilon}\Pr_{u\sim q_\phi(\cdot\mid x,H_t)}[u\text{ is improving from }x] p ⋆ ( ε ) := min x : m a x X F ⋆ − F ⋆ ( x ) ≥ ε Pr u ∼ q ϕ ( ⋅ ∣ x , H t ) [ u is improving from x ] , uniformly over histories H t H_t H t . We assume p ⋆ ( ε ) > 0 p^\star(\varepsilon)>0 p ⋆ ( ε ) > 0 .
Theorem 3 (Single-step reachability). Under Assumption 1, at any step at which no beam member is ε \varepsilon ε -optimal, the step’s ∣ C t − 1 ∣ k |C_{t-1}|k ∣ C t − 1 ∣ k proposals contain one that improves on its parent with probability at least 1 − ( 1 − p ⋆ ( ε ) ) ∣ C t − 1 ∣ k = : p s t e p ( ε ) 1-(1-p^\star(\varepsilon))^{|C_{t-1}|k} =: p^{\mathrm{step}}(\varepsilon) 1 − ( 1 − p ⋆ ( ε ) ) ∣ C t − 1 ∣ k =: p step ( ε ) .
Theorem 4 (Convergence rate). Under the scored form of coverage (Assumption 5) at tolerance ε \varepsilon ε , let h ~ 0 \widetilde{h}_0 h 0 be the seed’s gap to the scored optimum, K : = ⌈ ( h ~ 0 − ε ) / Δ min ⌉ K := \lceil(\widetilde{h}_0-\varepsilon)/\Delta_{\min}\rceil K := ⌈( h 0 − ε ) / Δ m i n ⌉ for improvement size Δ min \Delta_{\min} Δ m i n , and p a d v ( ε ) p^{\mathrm{adv}}(\varepsilon) p adv ( ε ) a lower bound on the probability that the leader’s k k k proposals improve it by at least Δ min \Delta_{\min} Δ m i n . Then T ≥ ( 2 K + 8 ln ( 1 / δ ) ) / p a d v ( ε ) T \ge(2K+8\ln(1/\delta))/p^{\mathrm{adv}}(\varepsilon) T ≥ ( 2 K + 8 ln ( 1/ δ )) / p adv ( ε ) steps suffice for the leader to be ε \varepsilon ε -optimal on the scored objective with probability at least 1 − δ 1-\delta 1 − δ .
Either W W W or k k k drives the per-step failure probability to zero exponentially. Coverage gates only these two rates, so when it fails the search stalls rather than regresses. Terminal quality also depends on the utility’s structure: under γ \gamma γ -submodularity with monotone gains, block-pass greedy is exact when each mutable block contributes one alternative (Proposition 4), and elitist beam on the same draws stays ahead of greedy until they separate (Proposition 5).
The Price of the Constraints
Proposition 2 (Price of freezing). At the seed ordering ( Π = { π ( 0 ) } ) (\Pi= \{ \pi^{(0)} \}) ( Π = { π ( 0 ) }) , with v i ( 0 ) ∈ V ~ i v_i^{(0)} \in\widetilde{\mathcal{V}}_i v i ( 0 ) ∈ V i , submodularity ratio γ > 0 \gamma> 0 γ > 0 (Definition 16 ) and diminishing returns on frozen coordinates (Corollary 3), with x a l l ⋆ x^\star_{\mathrm{all}} x all ⋆ the optimum over the all-mutable space and x m u t ⋆ x^\star_{\mathrm{mut}} x mut ⋆ the unregularised optimum over the mutable space
F ⋆ ( x a l l ⋆ ) − F ⋆ ( x m u t ⋆ ) ≤ 1 γ ∑ i ∈ I i m m max v ∈ V ~ i [ F ⋆ ( x ( 0 ) [ i : = v ] ) − F ⋆ ( x ( 0 ) ) ] . (9) F^\star(x^\star_{\mathrm{all}})-F^\star(x^\star_{\mathrm{mut}})\le\frac{1}{\gamma}\sum_{i\in I_{\mathrm{imm}}}\max_{v\in\widetilde{\mathcal{V}}_i}\left[F^\star(x^{(0)}[i:=v])-F^\star(x^{(0)})\right]. \tag*{(9)} F ⋆ ( x all ⋆ ) − F ⋆ ( x mut ⋆ ) ≤ γ 1 i ∈ I imm ∑ v ∈ V i max [ F ⋆ ( x ( 0 ) [ i := v ]) − F ⋆ ( x ( 0 ) ) ] . (9)
Theorem 5 (Regularisation bias). For any λ ≥ 0 \lambda\ge0 λ ≥ 0 and κ ≥ 0 \kappa\ge0 κ ≥ 0 , F ⋆ ( x m u t ⋆ ) − F ⋆ ( x λ ⋆ ) ≤ λ ⋅ κ ( x m u t ⋆ ) F^\star(x^\star_{\mathrm{mut}})-F^\star(x^\star_\lambda)\le\lambda\cdot\kappa(x^\star_{\mathrm{mut}}) F ⋆ ( x mut ⋆ ) − F ⋆ ( x λ ⋆ ) ≤ λ ⋅ κ ( x mut ⋆ ) .
We write x ⋆ : = x m u t ⋆ = x λ ⋆ x^\star:= x^\star_{\mathrm{mut}} = x^\star_\lambda x ⋆ := x mut ⋆ = x λ ⋆ at λ = 0 \lambda=0 λ = 0 , as in every reported run. Both prices are small when the constraints are used as intended: contract blocks carry little task reward, and λ \lambda λ breaks ties toward shorter prompts. The terminal-quality results rest on γ \gamma γ , for which we have no per-benchmark estimator. These bounds give the cost of freezing, not whether freezing is needed or enough; § 4 tests that.
Experiments
Our experiments address two questions. (Q1) Does the batched iterative proposer–scorer template of Definition 14, instantiated with elitist beam search and lineage-aware diversity, translate the
caption: Table 2: Optimized for model: GPT-3.5-Turbo; datasets: ARC-Challenge, GSM8K [37 ] . Evoke is Hu et al. [35 ] .
:::
deterministic monotonicity of Lemma 1 into measurable gains on standard prompt-optimization benchmarks? (Q2) Are those gains robust across target models, task families, and prior-work evaluation protocols, or are they an artifact of a single setting? To answer both we reproduce, without modification , the published protocols of five recent prompt-optimization papers and compare SPLICE against their reported baselines—no re-tuning of their pipelines, no substitution of their target models.
SETUP. We evaluate SPLICE on seven public benchmarks spanning sentiment classification (SST-5 [75 ] ), mathematical reasoning (GSM8K [14 ] , AIME-2025 [4 ] ), commonsense and multi-step reasoning (ARC-Challenge [13 ] , BBH [76 ] ), privacy-conscious delegation (PUPA [73 ] ), and expert-level science QA (GPQA-Diamond [64 ] ). For every benchmark we adopt the target model and evaluation protocol of the corresponding published baseline [1 , 37 , 65 , 89 , 94 ] : GPT-4.1 Mini [1 ] (AIME-2025, PUPA), GPT-3.5-Turbo [37 ] (ARC, GSM8K), Claude Haiku 4.5 [65 ] (BBH, GPQA-Diamond), Gemma-3-27B [89 ] and DeepSeek-V3.2 [94 ] (SST-5); example optimized prompts are in Section A, further experiments in Section F.
DISCUSSION. Table 2 to Table 4 together cover six of the seven benchmarks; the seventh, SST-5, is Table 7 (Section F). Baselines are as published and report no seed variance, so we call a margin of at most 0.5 pp a match . On that accounting SPLICE wins on four benchmarks (SST-5, AIME-2025, GSM8K, BBH) and matches the strongest prior method on three (ARC-Challenge at +0.5 pp, GPQA-Diamond at 0.0, and PUPA at −0.22 pp against GEPA+Merge). The largest gains are +5.1 pp on AIME-2025 over GEPA and +2.9 pp on SST-5/gemma-3-27b-it; GSM8K and BBH are narrow (+0.69, +0.70 pp). Two patterns recur. First, margins track headroom : the lead is largest where prior baselines sit well below the task’s oracle ceiling and tightens on near-saturated benchmarks (PUPA, BBH); GPQA-Diamond, a tie despite headroom, is the exception. Second, rank is stable across settings : on every one of the five target models we tried, SPLICE is at worst within the matching threshold of the best published method, spanning proprietary (GPT-4.1 Mini, GPT-3.5-Turbo, Claude Haiku 4.5) and open-weight (Gemma-3-27B, DeepSeek-V3.2) tiers.
Table 4. Optimized for model: Claude Haiku 4.5; datasets: BBH, GPQA-Diamond [65 ] .
Table 2.
Table 7. Benchmark results on SST-5 across two evaluation protocols. Gemma-3-27B numbers follow [89 ] ; DeepSeek-V3.2 numbers follow [94 ] . “—” indicates the method was not run under the corresponding protocol. SPLICE is the test mean over three runs; baselines are as published. Bold marks the best score per column.
Ablations
We study the contribution of each axis of SPLICE in isolation; the proposer is fixed and the sweeps vary the target (except Figure 3 ). On SST-5 the target spans five capacity tiers with two models per tier: Micro: gemma-3-4b-it, nemotron-nano-9b-v2; Tiny: gemma-3-12b-it, nemotron-nano-12b-v2; Small: qwen3-32b (S1), nemotron-nano-30b (S2); Large: nemotron-super-3-120b (L1), qwen3-vl-235b-a22b (L2); Frontier: claude-sonnet-4-6 (F1), claude-opus-4-6 (F2), and on ARC-Challenge and GPQA-Diamond across these six (S1–F2). We compare four selectors spanning the iterative / non-iterative divide: Best-of-N N N (BoN; a single step of Definition 14 that keeps the best of N N N children and drops the seed), Greedy (W = 1 W=1 W = 1 , children only), Beam (W > 1 W>1 W > 1 , children only), and Elitist Beam (Algorithm 2), which realises the guarantee of Lemma 1, and that of Theorem 1 when D ≥ 1 D \ge1 D ≥ 1 (D = 0 D=0 D = 0 in the GPQA sweep, D = 1 D=1 D = 1 on SST-5).
Figure 3. Best-of-N N N scaling with proposer size. Fitted one-shot accuracy rises with proposer size at every N N N , while the N N N -curves overlap within each size band: more samples do not substitute for scale.
WHY MUTABILITY: A CONTRACT STRESS TEST. We add a seven-clause contract (tool schema, safety text, output envelope, business rule) to SST-5 on gemma-3-27b-it, including POLICY-1: escalate any snippet mentioning “film” or “movie” ; the proxy reward is accuracy, so obeying it (26% of examples) forfeits reward. The same optimizer (§ 2 ) runs in four arms that differ only in the contract’s mutability: A1 frozen (∣ V i ∣ = 1 |V_i|=1 ∣ V i ∣ = 1 ), A2 all-mutable, A3 one monolithic editable block, as most prior methods search, and A4 editable plus “do not edit”. The ordering inverts (Figure 2 ): every editable arm beats A1 by ≈ 10 \approx10 ≈ 10 pp on the proxy and loses by ≈ 17 \approx17 ≈ 17 pp on the contract-aware objective, while the other contract classes were untouched by every arm: optimizers trade away exactly the clauses that cost reward. Freezing is therefore needed, since instruction does not protect the clause, but it does not suffice: it protects text, not effect, and A1’s compliance (66.8%) is below the unoptimized seed’s 96.5% (details: Section F.2).
Figure 2. Editable contracts win on the proxy reward but lose on the contract-aware objective. SST-5, gemma-3-27b-it, mean ± \pm ± s.d. over three paired seeds. (a) Endpoints are different metrics on different splits; only the ordering is meaningful. (b) Only SPLICE keeps the clause partly in force (full numbers: Table 11 , Section F.2).
BEST-OF-N N N SCALING. We characterize the weakest iterative regime first: Best-of-N N N sampling with no feedback. Figure 3 , from a separate run that varies the proposer, reports Best-of-N N N accuracy across proposer sizes and N ∈ { 1 , 3 , 5 , 10 , 15 } N \in\{1, 3, 5, 10, 15\} N ∈ { 1 , 3 , 5 , 10 , 15 } on SST-5 and GPQA-Diamond. One-shot accuracy scales strongly with proposer capacity: on SST-5 it rises from ∼ 45 % \sim45\% ∼ 45% for the smallest proposers to ∼ 55 % \sim55\% ∼ 55% for the largest. But the five N N N -curves lie within a narrow band at every proposer size; with the proposer fixed, the GPQA target sweep shows no reliable N N N -trend either (Figure 16 , ± 20 \pm20 ± 20 pp per cell difference). Drawing more samples from the same seed without feedback is not a reliable substitute for capacity or for iteration; beam width is discussed in Section F.3.1.
Figure 16. BoN scaling by tier on GPQA-Diamond. Accuracy is non-monotonic in N N N ; the overall and small-tier curves peak at N = 10 N=10 N = 10 , and small models gain most.
ROLE OF CRITIQUE SIGNAL. The next component is the critique signal: the appended textual gradient that the proposer conditions on. Figure 4 a adds critique to BoN and reports the paired comparison on SST-5, averaged across multiple target models (Figure 4 a). At every N N N the critique-on variant outperforms critique-off by +1.2 to +1.7 pp. Per-arm 95% CIs overlap, so the evidence is the consistent sign across N N N . The gap is largest at N N N =10 (+1.7 pp) and does not shrink systematically with N N N , consistent with textual gradients carrying information that raw sampling does not supply.
Figure 4. Critique and elitist iteration each add accuracy on SST-5. (a) Critique adds 1.2–1.7 pp to Best-of-N N N at every N N N : BoN (grey) vs. BoN+critique (gold), per-N N N gap in red; 95% bootstrap CIs over the target models overlap at every N N N . (b) Elitist search leads one-shot sampling: test accuracy, mean over the two SST-5 protocol targets (Table 7 ).
GAINS FROM ITERATIVE OPTIMIZATION. Iteration with an elitist selector is what turns critique into durable progress. Figure 4 b compares iterative strategies (Greedy, Beam, Elitist Beam) against BoN with the same proposer model on SST-5, and Figure 12 (Section F) on ARC-Challenge. On both, Elitist Beam scores highest of all strategies; on the HelpSteer2 judge task BoN falls below the seed (Section F.5). Elitist Beam leads the best plain BoN configuration by +3.7 pp on SST-5 (averaged over its two protocol targets) and by +1.3 pp on GPQA-Diamond, inside that sweep’s noise; on saturated ARC-Challenge the strategies sit within 1 pp of each other. Since the proposer is identical across strategies, the gain comes not from proposer capacity but from the scoring–proposal feedback loop with elitist retention (Theorem 3 composed with Lemma 1).
Figure 12. On ARC-Challenge the strategies compress. Validation accuracy, mean over the six target models S1–F2. The SST-5 counterpart is Figure 4 b.
PROPOSER AND TARGET CAPACITY. Fitted one-shot accuracy rises with proposer size at every N N N (Figure 3 a and Figure 3 b). With the proposer fixed and the target varied (GPQA), iterative strategies lead on the frontier tier but not on the small tier (Figure 15 ), since a weak target bounds what any prompt achieves.
Figure 15. GPQA strategy comparison by model tier. Beam and Elitist Beam lead on frontier models and Elitist Beam on large ones; on small models no strategy consistently wins. Tick label “w w w =4” is the beam width W W W =4.
SEARCH STRATEGY AND DIVERSITY. At matched W W W =4 on BBH, varying only the number of diversity slots, D D D =0 stays near 0.21 for all 13 steps (the beam never escapes a single mode) while every D ≥ 1 D \ge1 D ≥ 1 variant exceeds 0.92 by step 4 (Table 12 , Section F); elsewhere the knob is far weaker, so diversity slots are insurance against collapse rather than a uniform gain (search trees: Figure 13 , Section F). Figure 14 (Section F) traces validation score along each run’s best-path lineage: on frontier targets the best paths gain +20 to +22.5 pp over the seed in three to four nodes, while L1 needs six nodes to cover a +47.5 pp gap (27.5%→75%); the leader is non-decreasing along the best path (Lemma 1) and climbs most in the first two steps (Section F.4.1).
Table 12. Removing the diversity slot collapses the search on BBH. The four div∗ ^* ∗ rows share beam width W = 4 W=4 W = 4 and differ only in the number of reserved diversity slots D D D , which makes this the clean control for Theorem 1. Without diversity the run is near 0.21 for all 13 steps (every beam member converges to a near-identical score and the search never escapes a single mode), while every D ≥ 1 D \ge1 D ≥ 1 variant reaches above 0.92 by step 4. This is the largest single-component effect we measure anywhere in the paper. ‡ ^\ddagger ‡ elitist_fullbatch is not a diversity control: it differs from the div∗ ^* ∗ rows on two axes (W = 6 W=6 W = 6 , D = 1 D=1 D = 1 ) and is included only as a wider-beam reference point; because two axes differ it cannot show whether width substitutes for diversity. ∗ ^* ∗ Best score on the step’s training batch (216 examples): it measures escape from a mode, not test accuracy. The diversity mechanism that ran is the distinct-parent slot with backfill (§ 2 ). Every row is a single seed (random_seed=42), so the collapse is unreplicated, and the same knob has small or no effect on ARC, GPQA and HelpSteer2 (§ 4 ). The claim we make is conditional: diversity is insurance against mode collapse and it pays where collapse is a live risk.
Figure 13. (Search trees, frontier models.) Rows: selection strategies (Greedy, Beam W = 4 W=4 W = 4 , Elitist Beam); columns: frontier target models. Node color encodes validation score (red = low, green = high); the red path is the best-candidate lineage. Greedy produces narrow ∼ \sim ∼ 19-node chains: once it finds a good candidate, it commits. Beam generates bushy 61–97-node trees exploring many parallel lineages. Elitist Beam sits between at ∼ \sim ∼ 40 nodes.
Figure 14. Candidate Lineage. Validation score along the best-scoring lineage for four GPQA-Diamond runs; x x x -axis is the search step, each tick labelled with the best-path node at that step. Frontier targets (F1, F2) reach their best score in 3–4 nodes counting the seed; L1 needs 6. The Greedy run (rightmost) improves at steps 1, 2 and 5.
Limitations and Conclusion
Limitations. The guarantees are conditional. Proposal coverage gates only the rate results, so when it fails the search stalls rather than regresses; the terminal-quality results rest on the submodularity ratio γ \gamma γ , for which we have no estimator. Freezing preserves a contract’s text, not its effect: in § 4 the frozen clause survives in every candidate, yet behavioral compliance on test falls from 96.5% for the unoptimized seed to 66.8%, so frozen blocks still need a behavioral audit. SPLICE optimizes the reward it is given, so a misspecified reward is the dominant failure mode. Open problems: which neighboring edits erode a frozen clause, an estimator for γ \gamma γ , and a matched-budget cost comparison. Conclusion. Casting prompt optimisation as constrained search over an edit graph of selectively-mutable blocks, SPLICE carries guarantees with named assumptions and wins on four of seven benchmarks, matching on three. The open case is recursive: the optimized text is the optimizer’s own.
Acknowledgments and Disclosure of Funding
We thank Benjamin Wyant and Matt Yanchyshyn for their leadership and support of this work, and the anonymous reviewers and area chair, whose detailed feedback significantly improved the quality of this paper. This work was funded by Amazon Web Services, where all authors were employed while carrying it out; no third-party funding was received, and the authors declare no other competing interests.
Seed and Optimized Prompts
Seed Prompt for AIME
<role></role>
<objective>Solve the given math problem. Every Answer is a non-negative integer between 0 and 999 (inclusive).</objective>
<approach></approach>
<examples></examples>
<output_format>give the final answer in the form \boxed{N}, where N is an integer between 0 and 999.</output_format>
SPLICE’s Optimized Prompt for AIME, GPT-4.1 Mini
<role>You are a world-class competition mathematician with expertise across all domains: number theory, combinatorics, algebra, geometry, probability, and analysis. You are known for your meticulous calculations, creative problem-solving approaches, and systematic verification. You never rush — you break complex problems into manageable pieces and double-check each step before proceeding.</role>
<objective>Solve the given math competition problem. Produce a clear, rigorous, step-by-step solution. The final answer is always a non-negative integer between 0 and 999 (inclusive). Before stating your final answer, verify it through an independent check or sanity test.</objective>
<approach>Use this disciplined problem-solving framework:
Parse the problem precisely: Identify exactly what is being asked. Note whether the answer requires a modular reduction (e.g., mod 1000, mod 1000000007), a specific quantity, or a transformed result. Misreading the question is the #1 source of errors.
Identify the mathematical domain and select tools: Determine the core techniques needed (modular arithmetic, CRT, generating functions, PIE, Heron’s formula, coordinate geometry, recursion, casework, etc.).
Break into sub-problems: Decompose complex problems into smaller, independently verifiable steps. For each sub-step, compute carefully and verify before moving on.
Execute with extreme arithmetic care:
For modular arithmetic: reduce intermediate results frequently to keep numbers small.
For counting: clearly define what you’re counting, check for over/undercounting.
For algebra: expand and simplify carefully, checking each manipulation.
For geometry: verify formulas before applying, check units/dimensions.
Verify your answer: Use at least one of these checks:
Compute via an alternative method
Check small cases or boundary conditions
Verify the answer is in the valid range [0, 999]
For mod problems, confirm the reduction was applied correctly
Estimate the magnitude to see if the answer is reasonable
Critical pitfalls to avoid:
Forgetting to apply the final modular reduction
Off-by-one errors in counting (inclusive vs exclusive bounds)
Sign errors in algebraic manipulation
Miscounting cases in casework
Confusing permutations with combinations
Forgetting to account for symmetry or identical elements </approach>
<examples>
Example 1:
Input: Find the remainder when 2 100 2^{100} 2 100 is divided by 1000.
Output: We need 2 100 m o d 1000 2^{100} \bmod1000 2 100 mod 1000 .
Since 1000 = 8 × 125 1000 = 8 \times125 1000 = 8 × 125 , we use CRT.
2 100 m o d 8 = 0 2^{100} \bmod8 = 0 2 100 mod 8 = 0 (since 2 3 = 8 2^3 = 8 2 3 = 8 divides 2 100 2^{100} 2 100 ).
2 100 m o d 125 2^{100} \bmod125 2 100 mod 125 : Using repeated squaring.
2 10 = 1024 ≡ 24 ( m o d 125 ) 2^{10} = 1024 \equiv24 \pmod{125} 2 10 = 1024 ≡ 24 ( mod 125 )
2 20 = 24 2 = 576 ≡ 76 ( m o d 125 ) 2^{20} = 24^2 = 576 \equiv76 \pmod{125} 2 20 = 2 4 2 = 576 ≡ 76 ( mod 125 )
2 40 = 76 2 = 5776 ≡ 26 ( m o d 125 ) 2^{40} = 76^2 = 5776 \equiv26 \pmod{125} 2 40 = 7 6 2 = 5776 ≡ 26 ( mod 125 )
2 80 = 26 2 = 676 ≡ 51 ( m o d 125 ) 2^{80} = 26^2 = 676 \equiv51 \pmod{125} 2 80 = 2 6 2 = 676 ≡ 51 ( mod 125 )
2 100 = 2 80 × 2 20 ≡ 51 × 76 = 3876 ≡ 1 ( m o d 125 ) 2^{100} = 2^{80} \times2^{20} \equiv51 \times76 = 3876 \equiv1 \pmod{125} 2 100 = 2 80 × 2 20 ≡ 51 × 76 = 3876 ≡ 1 ( mod 125 ) CRT: x ≡ 0 ( m o d 8 ) x \equiv0 \pmod{8} x ≡ 0 ( mod 8 ) , x ≡ 1 ( m o d 125 ) x \equiv1 \pmod{125} x ≡ 1 ( mod 125 ) .
x = 125 k + 1 x = 125k + 1 x = 125 k + 1 , need 125 k + 1 ≡ 0 ( m o d 8 ) → 5 k ≡ 7 ( m o d 8 ) → k ≡ 3 ( m o d 8 ) 125k + 1 \equiv0 \pmod{8} \to5k \equiv7 \pmod{8} \to k \equiv3 \pmod{8} 125 k + 1 ≡ 0 ( mod 8 ) → 5 k ≡ 7 ( mod 8 ) → k ≡ 3 ( mod 8 ) .
x = 125 ( 3 ) + 1 = 376 x = 125(3) + 1 = 376 x = 125 ( 3 ) + 1 = 376 .
376 \boxed{376} 376
Example 2:
Input: How many ways can you arrange the letters in BANANA?
Output: BANANA has 6 letters: B(1), A(3), N(2).
Distinct arrangements = 6 ! / ( 1 ! × 3 ! × 2 ! ) = 720 / 12 = 60 = 6!/(1! \times3! \times2!) = 720/12 = 60 = 6 ! / ( 1 ! × 3 ! × 2 !) = 720/12 = 60 .
60 \boxed{60} 60
Example 3:
Input: In triangle A B C ABC A B C , A B = 13 AB = 13 A B = 13 , B C = 14 BC = 14 B C = 14 , C A = 15 CA = 15 C A = 15 . Find the area of triangle A B C ABC A B C .
Output: Using Heron’s formula with s = ( 13 + 14 + 15 ) / 2 = 21 s = (13 + 14 + 15)/2 = 21 s = ( 13 + 14 + 15 ) /2 = 21 .
Area = 21 × 8 × 7 × 6 = 7056 = 84 = \sqrt{21 \times8 \times7 \times6} = \sqrt{7056} = 84 = 21 × 8 × 7 × 6 = 7056 = 84 .
Verification: With base B C = 14 BC = 14 B C = 14 , height h = 2 ( 84 ) / 14 = 12 h = 2(84)/14 = 12 h = 2 ( 84 ) /14 = 12 . Check: 13 2 = 5 2 + 12 2 = 169 13^2 = 5^2 + 12^2 = 169 1 3 2 = 5 2 + 1 2 2 = 169 ✓
84 \boxed{84} 84
Example 4:
Input: A fair six-sided die is rolled 4 times. What is the probability that the sum is 10? Express your answer as p / q p/q p / q in lowest terms and find p + q p + q p + q .
Output: We need the number of solutions to d 1 + d 2 + d 3 + d 4 = 10 d_1 + d_2 + d_3 + d_4 = 10 d 1 + d 2 + d 3 + d 4 = 10 where 1 ≤ d i ≤ 6 1 \le d_i \le6 1 ≤ d i ≤ 6 .
Substitute x i = d i − 1 x_i = d_i - 1 x i = d i − 1 , so x 1 + x 2 + x 3 + x 4 = 6 x_1 + x_2 + x_3 + x_4 = 6 x 1 + x 2 + x 3 + x 4 = 6 where 0 ≤ x i ≤ 5 0 \le x_i \le5 0 ≤ x i ≤ 5 .
Using inclusion-exclusion on stars and bars:
No restriction: ( 9 3 ) = 84 \binom{9}{3} = 84 ( 3 9 ) = 84
One x i ≥ 6 x_i \ge6 x i ≥ 6 : ( 4 1 ) ( 3 3 ) = 4 \binom{4}{1}\binom{3}{3} = 4 ( 1 4 ) ( 3 3 ) = 4
Two x i ≥ 6 x_i \ge6 x i ≥ 6 : impossible (sum would be ≥ 12 > 6 \ge12 > 6 ≥ 12 > 6 )
Favorable = 84 − 4 = 80 = 84 - 4 = 80 = 84 − 4 = 80 .
Total outcomes = 6 4 = 1296 = 6^4 = 1296 = 6 4 = 1296 .
Probability = 80 / 1296 = 5 / 81 = 80/1296 = 5/81 = 80/1296 = 5/81 .
p + q = 5 + 81 = 86 p + q = 5 + 81 = 86 p + q = 5 + 81 = 86 .
86 \boxed{86} 86
Example 5:
Input: Find the number of integers n n n with 1 ≤ n ≤ 1000 1 \le n \le1000 1 ≤ n ≤ 1000 such that n 2 + n n^2 + n n 2 + n is divisible by 6.
Output: n 2 + n = n ( n + 1 ) n^2 + n = n(n + 1) n 2 + n = n ( n + 1 ) , the product of two consecutive integers.
n ( n + 1 ) n(n + 1) n ( n + 1 ) is always even (divisible by 2), so we need n ( n + 1 ) n(n + 1) n ( n + 1 ) divisible by 3.
n ( n + 1 ) m o d 3 n(n + 1) \bmod3 n ( n + 1 ) mod 3 : if n ≡ 0 n \equiv0 n ≡ 0 : 0 × 1 ≡ 0 0 \times1 \equiv0 0 × 1 ≡ 0 ✓; if n ≡ 1 n \equiv1 n ≡ 1 : 1 × 2 ≡ 2 1 \times2 \equiv2 1 × 2 ≡ 2 ✗; if n ≡ 2 n \equiv2 n ≡ 2 : 2 × 0 ≡ 0 2 \times0 \equiv0 2 × 0 ≡ 0 ✓.
So n ( n + 1 ) n(n + 1) n ( n + 1 ) is NOT divisible by 3 when n ≡ 1 ( m o d 3 ) n \equiv1 \pmod{3} n ≡ 1 ( mod 3 ) .
Numbers 1–1000 with n ≡ 1 ( m o d 3 ) n \equiv1 \pmod{3} n ≡ 1 ( mod 3 ) : these are 1, 4, 7, . . . , 1000. Count = ( 1000 − 1 ) / 3 + 1 = 334 = (1000 - 1)/3 + 1 = 334 = ( 1000 − 1 ) /3 + 1 = 334 .
Answer = 1000 − 334 = 666 = 1000 - 334 = 666 = 1000 − 334 = 666 .
666 \boxed{666} 666
</examples>
<output_format>give the final answer in the form N \boxed{N} N , where N is an integer between 0 and 999.</output_format>
Table 1 (PDF p. 19).
\boxed{}, or any markup notation anywhere in your response. Write all calculations as plain text like: 3 × 4 = 12. Always produce a final whole number answer (no decimals, no trailing zeros, no commas in numbers).</role>
<objective>Solve the given math word problem. Before computing, carefully identify: (1) what quantity is being asked for, (2) any real-world facts needed but not stated (e.g., cars have 4 wheels, roller skates have 4 wheels each, a pair = 2 items, a dozen = 12), and (3) the correct direction of comparisons (e.g., “A costs twice as much as B” means A = 2 × B). Then solve step by step using plain arithmetic. Output ONLY a bare integer after #### on the final line.</objective>
<approach>Follow these steps:
Read the problem twice. Identify the exact question being asked. Note all units carefully — distinguish between groups vs individuals, per-person vs total, containers vs contents. When N people/items are excluded from an action, determine what unit that removes (e.g., “2 students didn’t eat” removes 2 complete servings, not 2 individual pieces).
State any real-world knowledge needed: common objects’ properties (wheels on vehicles, legs on animals, items in a pair/dozen), and any implicit facts the problem assumes you know.
Parse comparative relationships carefully. “A is/costs twice as much as B” means A = 2 × B (A is larger). “A is 5 less than 3 times B” means A = 3 × B − 5. Identify the base quantity and the derived quantity before computing.
Compute step by step using plain-text arithmetic (×, +, −, /). Calculate each intermediate value as a number before proceeding. Never leave expressions unevaluated. Never use variables, algebra, or any LaTeX/markup.
Verify: Does your answer match the exact question asked? Did you account for ALL items/people mentioned? Is it a whole number? Write it after “#### ” on the last line.
</approach>
<examples>
Example 1:
Input: A store had 120 shirts. They sold 1/3 of them on Monday and 1/4 of the remainder on Tuesday. How many shirts are left?
Output: The store started with 120 shirts. Sold on Monday: 120 × 1/3 = 40 shirts. Remaining after Monday: 120 − 40 = 80 shirts. Sold on Tuesday: 80 × 1/4 = 20 shirts. Remaining after Tuesday: 80 − 20 = 60 shirts.
60
Example 2:
Input: 5 cars are in a parking lot. How many wheels are there in total?
Output: There are 5 cars in the parking lot. Each car has 4 wheels (real-world fact). Total wheels: 5 × 4 = 20 wheels.
20
Example 3:
Input: A plot of land costs $40,000. Construction costs twice as much as the land. What is the total cost of land plus construction?
Output: Land cost: 40000 dollars. Construction costs twice as much as land: 2 × 40000 = 80000 dollars. Total cost: 40000 + 80000 = 120000 dollars.
120000
Example 4:
Input: A teacher bought 10 packs of crackers, with 8 crackers per pack, for her class. 2 students were absent and didn’t get any. How many crackers were eaten?
Output: Total packs: 10. Each pack has 8 crackers. Total crackers: 10 × 8 = 80 crackers. 2 students were absent, so 2 packs were not eaten. Crackers not eaten: 2 × 8 = 16 crackers. Crackers eaten: 80 − 16 = 64 crackers.
64
Example 5:
Input: A worker earns $12 per hour. She works 8 hours a day for 5 days. Her employer deducts $50 for insurance. What is her take-home pay?
Output: Hourly wage: 12 dollars. Daily earnings: 12 × 8 = 96 dollars. Weekly earnings: 96 × 5 = 480 dollars. After insurance deduction: 480 − 50 = 430 dollars.
430
</examples>
<output_format>Show your step-by-step reasoning, then on the final line output the answer as a single number after ‘#### ’. For example: ‘#### 42’. Do not include units, commas, or any text after the number.</output_format>
Seed Prompt for GPQA
<role>You are an expert scientist with deep knowledge in physics, chemistry, and biology. You approach problems methodically by identifying the relevant scientific principle first, then systematically evaluating each option.</role>
<objective>Answer the following multiple choice question by reasoning through it step by step, then selecting the correct answer.</objective>
<approach></approach>
<examples></examples>
<output_format>Think through the problem step by step. After your reasoning, state your final answer on a new line in the format: The answer is (X) where X is A, B, C, or D.</output_format>
SPLICE’s Optimized Prompt for GPQA, Claude Haiku 4.5
<role>You are an expert-level science examiner who solves graduate-level multiple choice questions with precision and efficiency. Your expertise spans physics, chemistry, biology, and mathematics including specialized topics like quantum mechanics, organic synthesis, molecular biology, optics, thermodynamics, and statistical mechanics. You are decisive: you commit to a solution path, execute it cleanly, and state your answer. You never ramble or restart calculations unnecessarily.</role>
<objective>Answer the multiple choice question below. Be concise and decisive. You MUST always end with your final answer in the required format — never leave it unstated, even if your reasoning feels incomplete.</objective>
<approach>Use this efficient reasoning strategy:
CLASSIFY: What type of problem is this?
ELIMINATE: Rule out obviously wrong options.
SOLVE: Apply the relevant principle ONCE. Do not restart.
MATCH & COMMIT: Match your result to the closest option.
ANSWER: State your final answer immediately.
CRITICAL RULES:
Keep reasoning to under 15 sentences.
If you catch yourself restarting, STOP and commit.
The final answer line is MANDATORY. </approach>
<examples>
Example 1:
Input: What is the ground state energy of a quantum harmonic oscillator with angular frequency ω \omega ω ? (A) 0 (B) ℏ ω / 2 \hbar\omega/2 ℏ ω /2 (C) ℏ ω \hbar\omega ℏ ω (D) 3 ℏ ω / 2 3\hbar\omega/2 3ℏ ω /2
Output: CLASSIFY: Conceptual recall — standard quantum mechanics formula. ELIMINATE: (A) is wrong — zero-point energy is nonzero. (D) is the energy of n = 1 n = 1 n = 1 state. SOLVE: Ground state (n = 0 n = 0 n = 0 ) has E = ℏ ω ( n + 1 / 2 ) = ℏ ω / 2 E = \hbar\omega(n + 1/2) = \hbar\omega/2 E = ℏ ω ( n + 1/2 ) = ℏ ω /2 . MATCH: This is option (B).
The answer is (B)
Example 2:
Input: A 2 kg block slides down a frictionless incline of 30° for 3 meters. What is its speed at the bottom? (A) 3.8 m/s (B) 5.4 m/s (C) 7.7 m/s (D) 9.8 m/s
Output: CLASSIFY: Calculation — energy conservation. ELIMINATE: (D) equals g g g , unlikely for this setup. SOLVE: Height = 3 × sin 30 ∘ = 1.5 3 \times\sin30^\circ= 1.5 3 × sin 3 0 ∘ = 1.5 m. v = 2 × 9.8 × 1.5 ≈ 5.42 v = \sqrt{2 \times9.8 \times1.5} \approx5.42 v = 2 × 9.8 × 1.5 ≈ 5.42 m/s. MATCH: Option (B).
The answer is (B)
</examples>
<output_format>Think through the problem step by step. After your reasoning, state your final answer on a new line in the format: The answer is (X) where X is A, B, C, or D.</output_format>
Seed Prompt for BBH
<role></role> <objective>Solve the reasoning task. Think step by step, then give the final answer.</objective> <approach></approach> <examples></examples> <output_format>Think through the problem step by step. After your reasoning, state your final answer on a new line starting with: The answer is</output_format>
SPLICE’s Optimized Prompt for BBH, Claude Haiku 4.5
<role>You are a precise reasoning engine. You solve problems step by step using plain text only — no markdown, no bold, no backticks, no special formatting. Your final line is always “The answer is” followed by the answer value. You never write anything after that final line.</role>
<objective>Solve the given reasoning task using step-by-step plain-text reasoning, then state your final answer.</objective>
<approach>Follow these steps:
Read the problem carefully. Think through it step by step in plain text.
Determine the correct answer. For pronoun resolution or ambiguity questions, choose the most natural and contextually supported interpretation.
Format your answer value according to the question type:
Multiple choice: lowercase letter in parentheses, e.g. (c)
Yes/no or true/false: just the word
Sorting or listing: items separated by spaces
Completion: only the missing part
Open-ended: the shortest correct answer
End with exactly one line: “The answer is” followed by your answer value.
STOP after that line. Do NOT repeat or write anything after it. </approach>
<examples> Example 1 (Multiple choice): Input: Which of the following is a fruit? Options: (a) carrot (b) apple (c) potato (d) spinach Output: Apples are fruits; carrots, potatoes, and spinach are vegetables. The answer is (b)
Example 2 (Yes/no): Input: If all roses are flowers and some flowers fade quickly, does it follow that some roses fade quickly? Answer yes or no. Output: The flowers that fade quickly may not be roses. The conclusion does not follow from the premises. The answer is no
Example 3 (Sorting): Input: Sort the following words alphabetically: pear apple orange banana Output: Alphabetical order: apple, banana, orange, pear. The answer is apple banana orange pear
Example 4 (Completion): Input: Complete the sequence: 2, 4, 8, 16, ___ Output: Each term is doubled. 16 times 2 equals 32. The answer is 32
Example 5 (Reasoning / pronoun resolution): Input: The trophy doesn’t fit into the brown suitcase because it is too large. What does “it” refer to? Options: (a) the trophy (b) the suitcase Output: If something does not fit because it is too large, the thing that is too large is the object trying to fit in, which in this case is the trophy. The answer is (a)
Example 6 (True/false): Input: Is the following statement true or false: “The sum of the interior angles of a triangle is 180 degrees.” Output: In Euclidean geometry, the interior angles of any triangle sum to 180 degrees. The answer is true </examples>
<output_format>Think through the problem step by step. After your reasoning, state your final answer on a new line starting with: The answer is</output_format>
Seed Prompt for ARC
<role>You have to solve the following science question.</role>
<objective>Analyze the science question, reason through all answer choices, and give your final answer inside <Answer></Answer> tags containing ONLY the letter A, B, C, or D.</objective>
<approach></approach>
<examples> Example 1: Input: What is the boiling point of water at standard atmospheric pressure? A) 50°C B) 100°C C) 150°C D) 200°C Output: Water boils at 100 degrees Celsius at standard atmospheric pressure. <Answer>B</Answer> </examples>
[Immutable suffix appended to every prompt]: After any reasoning, give your final answer inside <Answer></Answer> tags containing ONLY the letter A, B, C, or D.
SPLICE’s Optimized Prompt for ARC, GPT-3.5-Turbo
<role>You are a precise science reasoning expert. You read questions carefully, evaluate every answer choice against exact scientific definitions, and always select the answer that most directly addresses what the question asks — whether that answer is simple or highly technical. You do not let the framing or sophistication of an option override its accuracy.</role>
<objective>Analyze the science question and evaluate ALL answer choices before selecting your final answer. Consider why each option is correct or incorrect. When options seem equally plausible, use precise scientific definitions to distinguish them. Give your final answer inside <Answer></Answer> tags containing ONLY the letter A, B, C, or D.</objective>
<approach>Use this 5-step strategy:
CLASSIFY the question type — this determines your reasoning lens: • CAUSAL/CONSEQUENCE: “what happens when X?” or “what is the result of X?” → trace the MOST DIRECT causal chain from X to the effect; do not skip to secondary or downstream consequences. • MECHANISM/APPEARANCE: “why does X appear/seem. . . ?” → focus on the perceptual or observational mechanism, not intrinsic physical properties. • PROPERTY/IDENTIFICATION: “which property identifies X?” or “what state of matter is X?” → match precise scientific definitions to the property described. • STRUCTURAL/LAYER: “which layer does X?” → verify the spatial relationship (above/below/ad- jacent) explicitly.
IDENTIFY the core scientific concept and the exact qualifier being tested (e.g., “regardless of size,” “appears,” “most direct,” “solid,” “primarily”).
EVALUATE each answer choice (A, B, C, D) with a brief justification — explain why each is correct or incorrect using precise scientific definitions. Do not stop at the first plausible option.
CHALLENGE — Compare your top 2 candidates: (a) EXACT MATCH: Does this answer address what the question literally asks, or does it answer a related-but-different question? (b) CAUSAL DIRECTNESS: For causal questions, which answer is the most immediate consequence of the stated cause — not a secondary effect? (c) REFERENT CHECK: Confirm which entity, layer, or process the question names. Make sure your answer describes THAT entity, not an adjacent one.
SELECT the answer that best matches the question’s exact ask. If you are uncertain or running low on space, skip extended reasoning and immediately output your best answer in <Answer> tags.
</approach>
<examples>
Example 1 (Causal): Input: A large forest is cut down for lumber. What is the MOST DIRECT consequence for local wildlife? A) Global carbon dioxide levels increase significantly B) Animals lose their habitat and food sources C) Soil erosion increases over many decades D) Nearby rivers become warmer due to less shade
Output: Question type: CAUSAL/CONSEQUENCE — asks for the most direct consequence of forest removal for wildlife. A) CO2 _2 2 increase — a real effect of deforestation, but it operates at a global scale and is an atmospheric consequence, not a direct consequence FOR local wildlife. B) Animals lose habitat and food sources — forest removal directly eliminates the shelter and food that wildlife depend on. This is the immediate, first-order effect on wildlife. C) Soil erosion — a real long-term consequence, but it operates over decades and affects the land, not wildlife directly. D) Warmer rivers — a secondary physical effect; it may eventually affect aquatic life, but it is not the most direct consequence of forest removal for wildlife generally. Challenge (top 2: A vs B): A describes a global atmospheric consequence. B describes the direct, immediate effect on the animals themselves. The question asks for the most direct consequence FOR local wildlife — B is the precise match. Causal directness check: Forest removed → \rightarrow → habitat and food gone → \rightarrow → wildlife directly affected. B is the first-order link in the chain. <Answer>B</Answer>
Example 2 (Mechanism): Input: Frost forms on a cold window on a winter morning. Which process best describes how the frost formed? A) Condensation, as water vapor cools below the dew point B) Freezing, as liquid water droplets on the glass solidify overnight C) Deposition, as water vapor converts directly to ice without passing through a liquid phase D) Sublimation, as ice on nearby surfaces vaporizes and reattaches to the glass
Output: Question type: MECHANISM — asks which phase-change process produces frost. A) Condensation — gas to liquid phase change (produces dew, not frost). Only applies above 0°C. B) Freezing — liquid to solid. Requires liquid water already present; does not describe frost forming from air. C) Deposition — direct gas to solid phase change (water vapor → \rightarrow → ice), bypassing liquid entirely. This is exactly how frost forms on surfaces below 0°C. D) Sublimation — solid to gas (the reverse process). Describes ice disappearing, not forming. Challenge (top 2: A vs C): Both involve water vapor, but condensation produces liquid (dew, above freezing) while deposition produces solid ice (frost, below freezing). The window is below 0°C — deposition is the exact mechanism. Exact match check: The question asks which process describes how frost forms → \rightarrow → deposition directly answers this. <Answer>C</Answer>
Example 3 (Appearance): Input: Venus appears brighter than any other planet in the night sky as seen from Earth. What is the primary reason Venus appears so bright? A) Venus reflects a large amount of sunlight due to its thick cloud cover B) Venus is the planet closest to the Sun C) Venus has a very large diameter compared to other planets D) Venus emits its own light from volcanic activity
Output: Question type: MECHANISM/APPEARANCE — asks why Venus APPEARS bright from Earth, not what its intrinsic physical property is. A) High reflectivity from thick clouds — Venus has an albedo of ∼ \sim ∼ 0.65–0.70, reflecting most incoming sunlight. High reflectivity directly causes exceptional apparent brightness as seen from Earth. B) Closest to the Sun — Mercury is even closer to the Sun. More importantly, orbital proximity to the Sun does not determine how bright a planet appears from Earth; reflectivity and distance to Earth do. C) Large diameter — Jupiter and Saturn are far larger than Venus but appear dimmer. Size alone does not determine apparent brightness. D) Emits own light — planets reflect sunlight; they do not generate visible light. Volcanic emission is negligible. Challenge (top 2: A vs B): B answers “which planet is near the Sun” — a related but different question. A directly answers why Venus APPEARS bright from Earth through the reflectivity mechanism. Exact match check: Appearance → reflectivity mechanism → A. <Answer>A</Answer>
Example 4 (Structural): Input: Which layer of the Earth moves on top of the asthenosphere and is responsible for tectonic plate movement? A) Inner core B) Outer core C) Lithosphere D) Mesosphere Output: Question type: STRUCTURAL/LAYER — asks which layer sits ON TOP OF (above) the asthenosphere. A) Inner core — Earth’s deepest solid layer; does not interact with the asthenosphere. B) Outer core — liquid iron-nickel layer deep inside Earth; does not overlie the asthenosphere. C) Lithosphere — the rigid outer shell (crust + uppermost mantle) that sits directly on top of the semi-plastic asthenosphere and is divided into tectonic plates. D) Mesosphere (lower mantle) — lies BELOW the asthenosphere, not above it. Challenge (top 2: C vs D): The asthenosphere is the viscous middle layer. Lithosphere is above it; mesosphere is below. The question asks for the layer moving ON TOP — that is the lithosphere. Referent check: “moves on top of the asthenosphere” → above → lithosphere = C. <Answer>C</Answer> </examples>
[Immutable suffix appended to every prompt]: After any reasoning, give your final answer inside <Answer></Answer> tags containing ONLY the letter A, B, C, or D.
Related Work
We review NLO approaches, from prompt optimization, its most developed form, to the self-improvement loops and test-time search that share its structure (Section B.1), and then the optimization results our analysis builds on (Section B.2). Table 5 locates each NLO method along the axes of Definition 14.
Table 5. Every prompt optimizer we discuss or compare against, on the axes of our framework (Definition 14), grouped as in Section B.1. ✓: the method provides the property; ✗: it does not; ◐: partial, or asserted but not established. Column definitions and per-method notes follow the table (Section B.2).
Natural Language Optimization
Discrete search. The text that steers a model matters: prompt quality drives few-shot performance [9 ] , the right directive elicits stepwise reasoning [81 ] , and accuracy is sensitive even to the order of prompt parts [54 ] ; we study black-box optimization of discrete text [51 ] , leaving aside soft prompts that require gradient access [44, 46]. Early methods searched tokens or phrases by gradients [71 ] , a learned policy [19 ] or edit operators [61 ] , with feedback that does not describe what failed. APE [93 ] and instruction induction [32 ] ` let an LLM propose whole instructions and keep the best, a single step with a greedy selector in the terms of Definition 14.
Textual feedback. ProTeGi [62 ] introduced the textual gradient , a natural-language account of minibatch errors that drives a beam over edits; its beam keeps only new children, so a strong parent can be lost. Successors enrich the signal: score histories [83 ] , positive gradients and momentum [15 , 47 ] , feedback from correct predictions to curb drift [17 , 82 ] , contrasted reasoning traces [65 ] , author–reviewer loops [35 ] , aggregated feedback [3 ] , and tree search over edit sequences [79 ] . StraGo [82 ] names the failure we target, a revision that fixes current errors but breaks passing examples, and answers it with better guidance rather than a selection rule. Feedback and search have also been applied to whole programs: DSPy [39 ] and MIPROv2 [60 ] compile per-module prompts by searching over instruction and demonstration candidates, while TextGrad [87 ] , LLM-AutoDiff [85 ] (implemented in the AdaFlow library) and Trace [11 ] back-propagate textual feedback through computation graphs. These systems optimize every prompt in a program; they structure the pipeline, whereas we structure the interior of one artifact, so the two compose. These frameworks already hold some text fixed. An AdaFlow prompt template is routinely assembled from several parameters (for example a task description and few-shot demonstrations), each marked as optimized or not; a TextGrad prompt can be split into several variables with gradients disabled on some; and DSPy, MIPROv2 and GEPA optimize instructions and demonstrations while the signature’s field and format scaffold stays fixed. Each amounts to section-level freezing set by the framework or the user. None poses it as a constraint of the optimization problem, pairs it with section-local critique, or bounds what it costs. Any of these feedback operators could serve as our proposer q ϕ q_\phi q ϕ .
Evolutionary and reflective search. EvoPrompt [28 ] , Promptbreeder [25 ] and GAAPO [69 ] evolve prompt populations with LLM operators. GEPA [1 ] , the strongest published baseline on four of our seven benchmarks (counting GEPA+Merge on PUPA), mutates by reflecting on execution traces and draws parents from a Pareto front over per-instance scores. That front is the closest prior mechanism to our diversity slots, but it is defined over task instances rather than parentage, so children of one parent can fill it. (On SST-5 under the protocol we reproduce, the published GEPA number, 42.0, is below that paper’s unoptimized baseline, 44.6; we report it as published.)
Self-improvement loops. The idea of a system that rewrites its own components dates to the Gödel machine [68 ] , which accepts a self-modification only when it is provably beneficial. LLMs have made empirical versions of this loop practical. STOP [90 ] lets a scaffolding program improve itself, and Gödel Agent [86 ] lets an agent modify its own logic. ADA [34 ] has a meta-agent write new agents in code and keeps an archive of discoveries, the Darwin Gödel Machine [91 ] grows an archive of coding agents that edit their own source, and AFlow [92 ] searches agentic workflows with Monte Carlo tree search. FunSearch [66 ] and AlphaEvolve [59 ] pair an LLM proposer with an automatic evaluator to evolve programs. Promptbreeder [25 ] is the self-referential case within NLO, evolving the prompts that mutate prompts. These loops share the propose–score–retain skeleton of Definition 14, and most depart from it in the ways Section C names for GEPA and OPRO: proposals conditioned on an archive rather than one parent, and archives that grow without bound. Program search also anticipates selective mutability. FunSearch evolves a single function inside a fixed program skeleton, and AlphaEvolve evolves only the code blocks a user marks, leaving the rest fixed. What NLO has lacked is that design posed as part of the optimization problem at the granularity of a section inside a prompt, together with an account of what freezing costs; self-modifying agent loops, where the modified system is also the modifier, otherwise enforce such limits outside the search.
Test-time search. A parallel line spends compute at inference time on each query rather than once on the artifact. Self-consistency [78 ] and repeated sampling [8 ] aggregate or verify many samples, Tree of Thoughts [84 ] searches over intermediate reasoning, and self-critique refines a single response [55 , 72 ] . Snell et al. [74 ] show that allocating it adaptively between parallel samples and sequential revisions can be more effective than scaling model parameters. NLO moves the same search off the query path: the cost is paid once, and the improved artifact conditions every later query. The parallel-versus-sequential question reappears in our setting as the comparison between Best-of-N N N sampling and iterative search under a matched proposer (§ 4 ).
Structure and constraints. Recent work decomposes a prompt into sections: MPO [70 ] applies gradients to named sections, SAPO [42 ] edits role, context, task and format segments separately, and UniPrompt [37 ] edits task facets and compares greedy and beam variants, in effect a selector ablation in a structured space. None makes a segment unreachable or prices length. Cost-aware CAPO [88 ] penalizes relative token length in the objective, the same shape as our F − λ κ F-\lambda\kappa F − λκ , and we add the bias bound of Theorem 5; BPO [12 ] rewrites prompts toward human preferences in a single pass. Constraint-aware CAPO [20 ] , concurrent with this work, enforces tool-use, brevity and compliance requirements with a primal–dual method that prices violations, so a contract-breaking prompt remains feasible. Our mutability tags make it unreachable instead, and we reserve pricing for length, where growth is undesirable but not forbidden. The nearest prior practice is the parameter- and scaffold-level freezing of the program optimizers above, and the code-level freezing of program search. What we add is to make user-designated sections a property of the feasible set, with section-local critique and a bound on what freezing costs (Proposition 2).
Optimization Foundations
Combinatorial and noisy search. Greedy maximization of monotone submodular functions achieves ( 1 − 1 / e ) (1-1/e) ( 1 − 1/ e ) [57 ] , extended to approximately submodular objectives by the submodularity ratio [16 ] [see also 41, 56]; we use it for block-level greedy search and the price of freezing. Choosing among near-tied candidates on a finite batch is best-arm identification [2 , 24 , 38 ] , with random search [5 ] as a baseline. Beam search [52 ] , simulated annealing [40 ] and tabu search [26 ] are selectors over a shared state space and neighbourhood [33 ] ; the abstraction our edit graph adopts. Local search on tours [30 , 48 , 49 ] , neural architecture search [23 , 50 , 63 , 95 ] and model-based hyperparameter optimization [6 , 36 ] search structured spaces under expensive, noisy evaluation, and evolutionary computation supplies classical diversity mechanisms [18 , 27 , 31 , 43 ] ; our diversity slots act on parentage.
Theory of iterative search. Runtime analysis of evolutionary algorithms bounds the expected time for elitist search to reach an optimum [21 ] , and our convergence result is in the same spirit, with a proposer-competence condition, whose average-case proxy we measure, in place of a fixed mutation operator. For prompt optimization, existing analyses bound which candidate to evaluate or keep under noise [45 , 53 ] , the convergence of continuous relaxations [29 , 77 ] , or the choice of evaluation data [58 ] . None analyzes the search itself: whether the retained candidate can regress, whether a population collapses onto one parent’s children, or what a constraint costs. These are properties of a selector on a structured space, and Section E treats them.
Notes on Table 5 . The rows cover every prompt optimizer we discuss or report a number for; program-search systems (FunSearch, AlphaEvolve) are omitted since they optimize code, as are the hand-written prompts in the benchmark tables (task description, expert and CoT prompts). “Structure”: structured or modular prompt representation. “DualGrad”: both positive and negative textual gradients. “SecLocal”: gradients or updates at the level of named prompt sections. “Elitism”: parents can survive a step. “Diversity”: an explicit mechanism for preserving population diversity. “Immutable”: designated sections cannot be modified by any reachable edit. “Priced”: prompt length or cost enters the objective. “Theory”: formal guarantees about the search; ⊙ \odot ⊙ for ProTeGi marks a bandit selection procedure rather than a result about the search trajectory. ⊙ \odot ⊙ under “Immutable” marks a whole-variable freeze (TextGrad’s requires_grad=False, AdaFlow’s requires_opt=False) rather than a section inside a prompt. GEPA+Merge adds a system-aware crossover step to GEPA and coincides with it on every axis tabulated here. Two unrelated methods are both named CAPO: CAPOc o s t _{\mathrm{cost}} cost [88 ] is cost-aware and prunes candidates under a token budget, while CAPOc o n s t r _{\mathrm{constr}} constr [20 ] is concurrent constraint-aware work. Both earn “Priced”, and both retain candidates by truncation over parents and offspring, so both earn “Elitism”; neither can render a section unreachable, since CAPOc o n s t r _{\mathrm{constr}} constr enforces its constraints as Lagrangian penalties. SAPO instructs its generator to preserve segments judged strong, which we do not count as “Immutable” because the protection is a request to the proposer rather than a property of the space (§ 2 ).
Figure 5. A prompt as a block-structured state. (a) Most prior optimizers edit a deployed prompt as one string, so any proposed rewrite may touch any span, including the tool schema that downstream parsers consume and the privacy clause that survived review. (b) We represent the same prompt as a state x = ( v 1 , … , v m , π ) x=(v_1,\ldots,v_m,\pi) x = ( v 1 , … , v m , π ) : one variant per semantically coherent block, plus an admissible ordering (Definition 5). Mutable blocks (white) range over variant sets V i V_i V i that the proposer explores. Immutable blocks (shaded, locked) satisfy ∣ V i ∣ = 1 |V_i|=1 ∣ V i ∣ = 1 , so no state in the search space differs from the seed on those coordinates (Definition 3); the space itself preserves the contract text; whether the model still obeys it is measured in § 4 . (c) A deterministic render maps the state to a string, which the black-box model consumes to produce reward (Definitions 6 and 9). Because render is deterministic, frozen blocks appear in the rendered prompt verbatim. Most prior work optimizes the object in (a); the constrained problem of Definition 11 is posable only over the object in (b).
Framework Details
This section supplements the framework of § 2 with the two statements the main text cites but does not state, the edit-graph diameter (Proposition 3) and the well-definedness of proposals (Assumption 2), and with how existing methods sit in the batched search template as selectors (Section C.1).
Proposition 3 (Diameter of the edit graph). Let diam ( Π ) \operatorname{diam}(\Pi) diam ( Π ) denote the diameter of the permutation subgraph induced by the chosen ordering moves. Then
diam ( G ) ≤ ∑ i = 1 m 1 { ∣ V i ∣ ≥ 2 } + diam ( Π ) . (10) \operatorname{diam}(\mathcal{G}) \le\sum_{i=1}^{m} \mathbf{1}\{|V_i| \ge2\} + \operatorname{diam}(\Pi). \tag*{(10)} diam ( G ) ≤ i = 1 ∑ m 1 { ∣ V i ∣ ≥ 2 } + diam ( Π ) . (10)
Assumption 2 (Well-defined proposal distribution). For every x ∈ X x \in\mathcal{X} x ∈ X and history H t H_t H t , q ϕ ( ⋅ ∣ x , H t ) q_{\phi}(\cdot\mid x,H_t) q ϕ ( ⋅ ∣ x , H t ) is a probability distribution over edits whose support satisfies Apply ( x , supp q ϕ ( ⋅ ∣ x , H t ) ) ⊆ N ( x ) ∪ { x } \operatorname{Apply}(x,\operatorname{supp} q_{\phi}(\cdot\mid x,H_t)) \subseteq\mathcal{N}(x) \cup\{x\} Apply ( x , supp q ϕ ( ⋅ ∣ x , H t )) ⊆ N ( x ) ∪ { x } : no proposal can leave X \mathcal{X} X or write to an immutable block.
Algorithms as Selectors
The selectors compared in § 4 are instances of Definition 14 that differ in the retention rule. With Ψ t = F ^ ( ⋅ ; D v a l i d ) \Psi_t=\widehat{F}(\cdot;\mathcal{D}_{\mathrm{valid}}) Ψ t = F ( ⋅ ; D valid ) and the final-leader output rule: Best-of-N N N is a single step (T = 1 T=1 T = 1 , W = 1 W=1 W = 1 , k = N k=N k = N ) that keeps the best child and drops the seed; greedy is beam search with W = 1 W=1 W = 1 , top 1 ( F ∖ C t − 1 , Ψ ) \operatorname{top}_1(\mathcal{F} \setminus C_{t-1}, \Psi) top 1 ( F ∖ C t − 1 , Ψ ) : the best child replaces the parent even when it scores lower; beam search in the style of ProTeGi keeps the top-W W W children, S b e a m : = top W ( F ∖ C t − 1 , Ψ ) S^{\mathrm{beam}} := \operatorname{top}_W(\mathcal{F} \setminus C_{t-1}, \Psi) S beam := top W ( F ∖ C t − 1 , Ψ ) , dropping parents each step; elitist beam search keeps the top-W W W of the full frontier, top W ( F , Ψ ) \operatorname{top}_W(\mathcal{F}, \Psi) top W ( F , Ψ ) ; and the SPLICE solver extends the elitist rule with a diversity reservation read from candidate annotations (§ 2 ).
Figure 6. One template, four slots, and what each method plugs in. Top: batched iterative search (Definition 14). From C 0 = { x ( 0 ) } C_0 = \{x^{(0)}\} C 0 = { x ( 0 ) } , each step expands the beam into a frontier with a proposal model q ϕ q_\phi q ϕ , scores it with a scoring functional Ψ t \Psi_t Ψ t , keeps at most W W W candidates with a selector S t S_t S t , and after T T T steps returns one artifact through an output rule O \mathcal{O} O . Middle: the selectors compared in § 4 are instances that share every slot but the selector. Bottom: four published methods depart from the template, and the tinted cells are the slots each one widens. “Not named” marks a slot the paper does not specify for that method, not a claim that it matches the template.
The published baselines of § 4 are not re-run inside the template; their numbers come from the protocols we reproduce. Several of them are also not instances of Definition 14, and it is more useful to name the difference than to stretch the template over it. GEPA scores candidates by a Pareto preorder over per-instance results and keeps an unbounded archive; GEPA+Merge additionally recombines two parents, a move outside N ( x ) \mathcal{N}(x) N ( x ) ; MIPROv2 searches instruction–demonstration combinations without a parent or a local move; OPRO conditions each proposal on a meta-prompt over the top-scoring history rather than on one parent; and PromptAgent retains an unbounded tree with a visit-count bonus. OPRO is the closest case: it fits Definition 14 if the parent is taken as nominal and the meta-prompt is passed through H t H_t H t , which Definition 13 allows. Each method embeds into Definition 14 only after widening a named component (a vector-valued scoring functional, a multi-parent expansion, a parent-free proposal, an unbounded pool, a nominal parent), and we do not claim that the template’s component-by-component comparison transfers to them.
Casting the methods this way exposes the axes along which they differ (beam size W W W , parent survival, diversity, scoring set and output rule), and Table 5 records several of them (elitism, diversity, structure) for each prior method. The axes internal to the SPLICE solver are ablated in § 4 ; the external baselines are compared as whole systems.
Solver Details
This section collects the pseudocode and illustrations of the SPLICE loop described in § 2 , and the details of proposal generation.
Algorithm 1 The SPLICE solver.
input: initial state $x^{(0)} \in \mathcal{X}$; proposal model $q_{\phi}$; critique agent $M_{\mathrm{crit}}$; beam width $W$; diversity slots $D$; quality-gate ratio $\varrho \in [0,1]$; proposals per candidate $k$; horizon $T$; momentum window $w$; minimum improvement $\Delta_{\min}$; patience $T_{\mathrm{pat}}$; training data $\mathcal{D}_{\mathrm{train}}$; validation data $\mathcal{D}_{\mathrm{valid}}$; regularizers $\{R_j\}$ with weights $\{\lambda_j\}$.
Initialize: $C_0 \leftarrow \{x^{(0)}\}$; score $\widetilde{F}(x^{(0)}) \leftarrow F(x^{(0)};\mathcal{D}_{\mathrm{valid}})$.
Gradient history $G_0 \leftarrow \varnothing$.
for $t=1,\ldots,T$ do
// i. Re-run the beam on a training batch (critique evidence only).
Sample $B_t \subseteq \mathcal{D}_{\mathrm{train}}$; compute $F(x;B_t)$ and per-example outcomes $\forall x \in C_{t-1}$.
// ii. Dual, section-local critique, one per parent.
$\operatorname{Crit}_t(x) \leftarrow M_{\mathrm{crit}}(x,B_t\text{-outcomes of }x)\quad \forall x \in C_{t-1}$
// iii. Momentum context from the gradient trajectory and cached scores.
$\operatorname{Mom}_t \leftarrow \operatorname{BuildMomentum}(G_{t-1},\{\widetilde{F}(\operatorname{leader}(C_s))\}_{s<t},\{\widetilde{F}(x)\}_{x\in C_{t-1}};w,\Delta_{\min})$
// iv. Propose $k$ candidates per beam member (edit only mutable blocks).
$\mathcal{N}_t \leftarrow \bigcup_{x\in C_{t-1}}\{\operatorname{Apply}(x,u_j):u_j \overset{\mathrm{i.i.d.}}{\sim}q_{\phi}(\cdot\mid x,\widetilde{F}(x),\operatorname{Crit}_t(x),\operatorname{Mom}_t),j=1,\ldots,k\}$
Remove from $\mathcal{N}_t$ any duplicate of a member of $C_{t-1}$ or of an earlier element of $\mathcal{N}_t$.
// v. Evaluate new candidates on validation, once (cached scoring).
for $x\in\mathcal{N}_t$ do
$\widetilde{F}(x)\leftarrow F(x;\mathcal{D}_{\mathrm{valid}})-\sum_j\lambda_jR_j(x)$
end
// vi. Elitist selection with diversity slots (Algorithm 2).
$C_t\leftarrow \mathcal{S}^{\mathrm{elit\text{-}div}}_t(C_{t-1}\cup\mathcal{N}_t,\widetilde{F};W,D,\varrho,t)$
// vii. Record the leader change and the critique behind it.
$x_t^{L}\leftarrow \operatorname{leader}(C_t)$
$\Delta_t\leftarrow \widetilde{F}(x_t^{L})-\widetilde{F}(\operatorname{leader}(C_{t-1}))$
$G_t\leftarrow G_{t-1}\cup\{(t,g_t,\Delta_t)\}$, where $g_t$ is the summary of $\operatorname{Crit}_t(\operatorname{parent}(x_t^{L}))$, or a no-change marker if $x_t^{L}\in C_{t-1}$
// viii. Early stopping.
if the leader has gained less than $\Delta_{\min}$ over the last $T_{\mathrm{pat}}$ steps then
break
end
end
return $\hat{x}\leftarrow\operatorname{leader}(C_t)$ at the last completed step
Proposals
The proposer is conditioned on the parent, its cached validation score, its critique, and the momentum context,
( render ( x ) , F ~ ( x ) , Crit t ( x ) , Mom t ) (\operatorname{render}(x),\widetilde{F}(x),\operatorname{Crit}_t(x),\operatorname{Mom}_t) ( render ( x ) , F ( x ) , Crit t ( x ) , Mom t ) ,
where Mom t \operatorname{Mom}_t Mom t summarizes G t − 1 G_{t-1} G t − 1 together with recent leader scores and the current beam’s scores. All of it is fixed before any step-t t t proposal is drawn and is a function of the history H t H_t H t of Definition 13, which is what makes a parent’s k k k proposals i.i.d. given H t H_t H t . The proposer sees validation scores but never a validation example, and samples k k k structurally valid edits per parent at non-zero temperature, each confined to the mutable blocks. A proposal may also reorder the blocks, an ordering move in Π \Pi Π . Proposition 2 is stated at the seed ordering, Π = { π ( 0 ) } \Pi=\{\pi^{(0)}\} Π = { π ( 0 ) } , so it prices freezing for search confined to that ordering and says nothing about runs that reorder.
Section E gives the probability that a step’s draws contain an improving one (Theorem 3) and what is known about terminal quality (Proposition 4 and Remark 4).
Theory: Supporting Results and Proofs
This section extends § 3 : the notation, the assumptions the main text does not state, the results it only points to, and proofs of every result. Table 6 gives the assumptions behind each result.
Figure 7. The critique and the momentum context (illustrative content, on the running example of Figure 1). (a) The critique agent reads a parent’s traces on the training batch and returns, for each mutable block, what to keep (p i p_i p i ) and what to repair (n i n_i n i ), plus a directional summary g ( x ) g(x) g ( x ) (7). Frozen blocks receive no critique. The proposer edits the block the critique points at, here the directive, and leaves the frozen blocks byte-identical. (b) The proposer also sees the momentum context, the last w w w entries of the gradient trajectory (8): the direction behind each new leader and the leader’s gain Δ s \Delta_s Δ s , so it can keep following a direction that worked.
Figure 8. One selection step, with numbers (W = 4 W = 4 W = 4 , D = 1 D = 1 D = 1 , k = 3 k = 3 k = 3 , ϱ = 0.7 \varrho= 0.7 ϱ = 0.7 ). The four beam members each propose three children, and parents and children are ranked together on scores cached at first evaluation (Algorithm 2). The top W − D = 3 W - D = 3 W − D = 3 fill the elite slots; all are children of A or B. The leader score is ℓ = 0.71 \ell= 0.71 ℓ = 0.71 , so the quality gate is τ = ϱ ℓ ≈ 0.50 \tau= \varrho\ell\approx0.50 τ = ϱ ℓ ≈ 0.50 (dashed line). Carried beam members (A–D) have parents from an earlier step, shown as ·. PICKDIVERSE (Algorithm 3) scans the remaining candidates in score order and skips a 3 a_3 a 3 and b 2 b_2 b 2 , whose parents are already elites’ parents; c 1 c_1 c 1 is the first candidate above the gate with a new parent and takes the diversity slot. This is Tier 3: Tiers 1–2 admit nothing here, because the seed is not in this frontier and every other candidate descends from it. Had no candidate above τ \tau τ had a new parent, the slot would be backfilled with the best remaining candidate above τ \tau τ . With D = 0 D = 0 D = 0 the next beam would come from two parents only.
The analysis has two goals. First, to place the SPLICE solver on firm footing: each component of Section 2 other than the critique (selective mutability, elitist selection, diversity slots, and length regularization) is paired with a formal guarantee that makes its contribution precise rather than anecdotal. Second, to name what the experiments of Section 4 can check: some results predict a quantity an ablation measures, and others are not tested in this paper. Proofs follow each group of results.
Two optima, and which one every statement here targets. We write x a l l ⋆ x^\star_{\mathrm{all}} x all ⋆ for the maximizer of F ⋆ F^\star F ⋆ over the all-mutable space X a l l \mathcal{X}_{\mathrm{all}} X all . That is the right reference for pricing the constraints (Proposition 2) and the wrong one for analyzing the search, which never leaves X \mathcal{X} X . Throughout this section, therefore,
x ⋆ ∈ arg max x ∈ X F ⋆ ( x ) , (11) x^\star\in\underset{x \in\mathcal{X}}{\operatorname{arg\,max}}\ F^\star(x), \tag*{(11)} x ⋆ ∈ x ∈ X arg max F ⋆ ( x ) , (11)
the optimum over the constrained space with contract blocks frozen (the x m u t ⋆ x^\star_{\mathrm{mut}} x mut ⋆ of Proposition 2). The distinction is not cosmetic. Measured against x a l l ⋆ x^\star_{\mathrm{all}} x all ⋆ , a state that is optimal within X \mathcal{X} X may still be
Algorithm 2 $\mathit{S}_{t}^{\mathrm{elit\text{-}div}}$: elitist selection with diversity slots.
input: frontier $\mathcal{F}=C_{t-1}\cup\mathcal{N}_{t}$; regularized score $\widetilde{F}$; beam width $W$; diversity slots $D$; quality-gate ratio $\varrho\in[0,1]$; current step $t$.
output: next beam $C_t\subseteq\mathcal{F}$, $|C_t|\le W$.
// Degenerate cases.
if $D\le 0$ or $|\mathcal{F}|\le W$ or $\mathcal{N}_t=\varnothing$ then
return $\operatorname{top}_{W}(\mathcal{F};\widetilde{F})$
$D\leftarrow\min(D,W-1)$; // guarantee at least one elite slot
// Elite slots by score.
$\mathcal{E}\leftarrow\operatorname{top}_{W-D}(\mathcal{F};\widetilde{F})$
$\ell\leftarrow\max_{x\in\mathcal{E}}\widetilde{F}(x)$
$\tau\leftarrow\varrho\cdot\ell$; // quality floor relative to the leader
$\Lambda\leftarrow\bigcup_{x\in\mathcal{E}}(\operatorname{lineage}(x)\setminus\{\operatorname{id}(x)\})$
$P\leftarrow\{\operatorname{parent}(x):x\in\mathcal{E}\}$
$Q\leftarrow(\mathcal{F}\setminus\mathcal{E})$ sorted by $\widetilde{F}$ desc.
$\mathcal{K}\leftarrow\varnothing$
// Fill $D$ diversity slots.
for $j=1,\ldots,D$ do
$c\leftarrow\operatorname{PickDiverse}(Q,\Lambda,P,t,\tau)$ // Algorithm 3
if $c$ is none then
break
end
$\mathcal{K}\leftarrow\mathcal{K}\cup\{c\}$; $Q\leftarrow Q\setminus\{c\}$
$\Lambda\leftarrow\Lambda\cup(\operatorname{lineage}(c)\setminus\{\operatorname{id}(c)\})$
$P\leftarrow P\cup\{\operatorname{parent}(c)\}$
end
// Backfill any unfilled diversity slots above the floor.
$\mathcal{K}\leftarrow\mathcal{K}\cup\operatorname{top}_{D-|\mathcal{K}|}\{c\in Q:\widetilde{F}(c)\ge\tau\};\widetilde{F}$
return $\mathcal{E}\cup\mathcal{K}$ sorted by $\widetilde{F}$ desc.
Figure 9. Pricing growth (illustrative numbers). (a) The cost. κ l e n = max ( 0 , ratio − 1 ) \kappa_{\mathrm{len}}=\max(0,\operatorname{ratio}-1) κ len = max ( 0 , ratio − 1 ) . κ l e n \kappa_{\mathrm{len}} κ len is plotted against the length ratio len ( x ) / len ( x ( 0 ) ) \operatorname{len}(x)/\operatorname{len}(x^{(0)}) len ( x ) / len ( x ( 0 ) ) , with shortening free and growth charged. (b) What λ \lambda λ changes. For parent x x x , F ( x ; D v a l i d ) = 0.80 F(x;\mathcal{D}_{\mathrm{valid}})=0.80 F ( x ; D valid ) = 0.80 , ratio = 1.00 =1.00 = 1.00 , F ~ , λ = 0 = 0.800 \widetilde{F},\lambda=0=0.800 F , λ = 0 = 0.800 , and F ~ , λ = 0.05 = 0.800 \widetilde{F},\lambda=0.05=0.800 F , λ = 0.05 = 0.800 . For child x ′ x' x ′ , F ( x ′ ; D v a l i d ) = 0.81 F(x';\mathcal{D}_{\mathrm{valid}})=0.81 F ( x ′ ; D valid ) = 0.81 , ratio = 1.30 =1.30 = 1.30 , F ~ , λ = 0 = 0.810 \widetilde{F},\lambda=0=0.810 F , λ = 0 = 0.810 , and F ~ , λ = 0.05 = 0.795 \widetilde{F},\lambda=0.05=0.795 F , λ = 0.05 = 0.795 . The child gains 0.01 but is 30% longer. At λ = 0.05 \lambda=0.05 λ = 0.05 the growth costs 0.05 × 0.30 = 0.015 0.05\times0.30=0.015 0.05 × 0.30 = 0.015 , more than the gain, so the selector keeps the parent. Whatever λ \lambda λ is, the accuracy given up is at most λ ⋅ κ ( x ) \lambda\cdot\kappa(x) λ ⋅ κ ( x ) (Theorem 5). The tinted cells mark the candidate the selector prefers at each λ \lambda λ .
ε \varepsilon ε -suboptimal with no improving neighbor available, which would make Assumption 1 false and the target of Theorem 4 unreachable at any horizon; Section F.2 measures that residual gap at 10.5 pp on a deliberately expensive contract, so the difference is real rather than hypothetical. Every ε \varepsilon ε -optimality claim below is against the best feasible prompt, and the price of feasibility itself is Proposition 2’s separate subject.
What the concentration results need from the metric. Relating a batch score to the population score takes two properties of the metric.
Algorithm 3 PICKDIVERSE (mode=lineage): one diversity pick.
input : sorted-desc candidates Q; used-ancestor set Λ; used-parent set P; current step t; quality floor τ; gen(c) is the step at which c was proposed.
output : a diverse candidate c ∈ Q, or NONE.
// T1: brand-new lineage, born this step.
for c ∈ Q do
if F̃(c) < τ then
break
end
if (lineage(c) \ {id(c)}) ∩ Λ = ∅ and gen(c) = t then
return c
end
end
// T2: brand-new lineage, any generation.
for c ∈ Q do
if F̃(c) < τ then
break
end
if (lineage(c) \ {id(c)}) ∩ Λ = ∅ then
return c
end
end
// T3: at least a different immediate parent.
for c ∈ Q do
if F̃(c) < τ then
break
end
if parent(c) ∉ P then
return c
end
end
return NONE
Assumption 3 (Bounded, decomposable metric). The per-example score lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] (Definition 8), and the score of a batch is the mean of its per-example scores (3) .
Boundedness means, by Hoeffding’s lemma, that each centered score is sub-Gaussian with variance proxy σ 2 ≤ 1 / 4 \sigma^2 \le1/4 σ 2 ≤ 1/4 (Lemma 2). Decomposability is what lets a batch of n n n examples estimate the population score to within O ( n − 1 / 2 ) O(n^{-1/2}) O ( n − 1/2 ) . Accuracy and exact match satisfy both. Set-level metrics, such as macro-F 1 F_1 F 1 and the mean Spearman ρ \rho ρ of the judge task (Section F.5), are not decomposable, because they are not averages of per-example terms; ρ \rho ρ also ranges over [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] rather than [ 0 , 1 ] [0,1] [ 0 , 1 ] . Only the concentration results use Assumption 3, since they are the results that relate a batch score to the population score (Theorems 2 and 7 and Corollaries 1 and 2), and for set-level metrics they do not apply as stated. The remaining results (monotonicity, diversity, reachability, convergence on the scored objective, and the prices of regularization and mutability) do not relate a batch score to the population score, so they do not use Assumption 3 and hold for any scoring function.
Cached scores. We write F ^ n ( x ) \widehat{F}_n(x) F n ( x ) for F ( x ; S ) F(x;S) F ( x ; S ) on a sample S S S of n n n examples, so that F ~ ( x ) = F ^ n ( x ) − ∑ j λ j R j ( x ) \widetilde{F}(x)=\widehat{F}_n(x)-\sum_j\lambda_jR_j(x) F ( x ) = F n ( x ) − ∑ j λ j R j ( x ) with S = D v a l i d S=\mathcal{D}_{\mathrm{valid}} S = D valid . SPLICE scores a candidate on D v a l i d \mathcal{D}_{\mathrm{valid}} D valid when it is first evaluated and caches that score while the candidate stays in the beam; a state that leaves the beam and is later re-proposed verbatim is evaluated again (Section D). We call this the cached-scoring convention , and Lemma 1 needs nothing more. The definitions and results that treat F ~ ( ⋅ ) : = F ~ ( ⋅ ; D v a l i d ) \widetilde{F}(\cdot):=\widetilde{F}(\cdot;\mathcal{D}_{\mathrm{valid}}) F ( ⋅ ) := F ( ⋅ ; D valid ) as a function on X \mathcal{X} X (Definitions 15 and 17, Assumption 5, Theorems 3 and 4, Propositions 1 and 5, and Corollary 2) assume in addition that scores are cached per state: every evaluation of a state returns the same score, as with a deterministic system agent. Theorem 7(ii) covers the general case, where re-evaluations are priced by a factor T + 1 T+1 T + 1 . The exception is the re-evaluation regime of
Theorem 2 and Corollary 1, the alternative design in which every frontier member is re-scored on fresh examples at each step.
Probabilistic Preliminaries
We record the standard facts used below, so that every proof reduces to an explicit application of one of them.
Lemma 2 (Hoeffding’s inequality). Let Z 1 , … , Z n Z_1,\ldots,Z_n Z 1 , … , Z n be independent with Z j ∈ [ 0 , 1 ] Z_j \in[0,1] Z j ∈ [ 0 , 1 ] and Z ‾ = 1 n ∑ j Z j \overline{Z} = \frac{1}{n}\sum_j Z_j Z = n 1 ∑ j Z j . Then for any ε > 0 \varepsilon> 0 ε > 0 , Pr [ ∣ Z ‾ − E Z ‾ ∣ > ε ] ≤ 2 exp ( − 2 n ε 2 ) \Pr[|\overline{Z} - \mathbb{E}\overline{Z}| > \varepsilon] \le2\exp(-2n\varepsilon^2) Pr [ ∣ Z − E Z ∣ > ε ] ≤ 2 exp ( − 2 n ε 2 ) . Moreover Z ‾ − E Z ‾ \overline{Z} - \mathbb{E}\overline{Z} Z − E Z is sub-Gaussian with variance proxy σ 2 / n \sigma^2/n σ 2 / n where σ 2 ≤ 1 / 4 \sigma^2 \le1/4 σ 2 ≤ 1/4 .
Lemma 3 (Difference of independent sub-Gaussians). If U , V U,V U , V are independent, mean-zero, sub-Gaussian with variance proxies s 2 s^2 s 2 each, then U − V U-V U − V is mean-zero sub-Gaussian with proxy 2 s 2 2s^2 2 s 2 , so Pr [ U − V > ε ] ≤ exp ( − ε 2 / ( 4 s 2 ) ) \Pr[U-V>\varepsilon]\le\exp(-\varepsilon^2/(4s^2)) Pr [ U − V > ε ] ≤ exp ( − ε 2 / ( 4 s 2 )) .
Proof. The moment generating function of a sub-Gaussian with proxy s 2 s^2 s 2 satisfies E e θ U ≤ e θ 2 s 2 / 2 \mathbb{E}e^{\theta U}\le e^{\theta^2s^2/2} E e θ U ≤ e θ 2 s 2 /2 . By independence E e θ ( U − V ) ≤ e θ 2 s 2 / 2 e θ 2 s 2 / 2 = e θ 2 ( 2 s 2 ) / 2 \mathbb{E}e^{\theta(U-V)}\le e^{\theta^2s^2/2}e^{\theta^2s^2/2}=e^{\theta^2(2s^2)/2} E e θ ( U − V ) ≤ e θ 2 s 2 /2 e θ 2 s 2 /2 = e θ 2 ( 2 s 2 ) /2 , which is the proxy-2 s 2 2s^2 2 s 2 bound; the tail bound is the Chernoff optimization θ = ε / ( 2 s 2 ) \theta=\varepsilon/(2s^2) θ = ε / ( 2 s 2 ) .
Lemma 4 (Lower-tail Chernoff bound, explicit form). Let N T N_T N T be a sum of T T T Bernoulli indicators, each with conditional success probability at least p ∈ ( 0 , 1 ] p\in(0,1] p ∈ ( 0 , 1 ] given the past. Fix an integer K ≥ 1 K\ge1 K ≥ 1 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . If
T ≥ 2 K + 8 ln ( 1 / δ ) p , (12) T\ge\frac{2K+8\ln(1/\delta)}{p}, \tag*{(12)} T ≥ p 2 K + 8 ln ( 1/ δ ) , (12) then Pr [ N T < K ] ≤ δ \Pr[N_T<K]\le\delta Pr [ N T < K ] ≤ δ .
Proof. Because each indicator has conditional success probability at least p p p given the past, N T N_T N T stochastically dominates Bin ( T , p ) \operatorname{Bin}(T,p) Bin ( T , p ) : couple each indicator to a Bernoulli( p ) (p) ( p ) variable that it dominates pointwise, and sum. It therefore suffices to bound the lower tail of Y ∼ Bin ( T , p ) Y\sim\operatorname{Bin}(T,p) Y ∼ Bin ( T , p ) with mean μ = T p \mu=Tp μ = T p . The multiplicative Chernoff bound gives, for 0 < K < μ 0<K<\mu 0 < K < μ ,
Pr [ Y < K ] ≤ exp ( − ( μ − K ) 2 2 μ ) . \Pr[Y<K]\le\exp\left(-\frac{(\mu-K)^2}{2\mu}\right). Pr [ Y < K ] ≤ exp ( − 2 μ ( μ − K ) 2 ) .
Write β = ln ( 1 / δ ) \beta=\ln(1/\delta) β = ln ( 1/ δ ) . By (12), μ ≥ 2 K + 8 β \mu\ge2K+8\beta μ ≥ 2 K + 8 β . Then K ≤ μ / 2 K\le\mu/2 K ≤ μ /2 , so μ − K ≥ μ / 2 \mu-K\ge\mu/2 μ − K ≥ μ /2 and ( μ − K ) 2 2 μ ≥ ( μ / 2 ) 2 2 μ = μ 8 ≥ 2 K + 8 β 8 ≥ β \frac{(\mu-K)^2}{2\mu}\ge\frac{(\mu/2)^2}{2\mu}=\frac{\mu}{8}\ge\frac{2K+8\beta}{8}\ge\beta 2 μ ( μ − K ) 2 ≥ 2 μ ( μ /2 ) 2 = 8 μ ≥ 8 2 K + 8 β ≥ β . Hence Pr [ Y < K ] ≤ e − β = δ \Pr[Y<K]\le e^{-\beta}=\delta Pr [ Y < K ] ≤ e − β = δ .
Lemma 4 gives Theorem 4 an explicit requirement, (12), in place of an unspecified universal constant; it is additive rather than multiplicative in ln ( 1 / δ ) \ln(1/\delta) ln ( 1/ δ ) .
Edit-Graph Reachability
The diameter bound Proposition 3 is a worst-case statement about the geometry of X \mathcal{X} X : any two states are connected by at most m m u t + diam ( Π ) m_{\mathrm{mut}}+\operatorname{diam}(\Pi) m mut + diam ( Π ) primitive edits, and selective mutability reduces this by excluding immutable blocks from the replacement phase. But SPLICE does not enumerate neighborhoods; it samples from q ϕ q_\phi q ϕ , and progress at step t t t depends on whether an improving neighbor is among the W k W_k W k samples drawn.
Definition 15 (Improving proposal). For a state x x x and history H t H_t H t , a proposal u ∼ q ϕ ( ⋅ ∣ x , H t ) u\sim q_\phi(\cdot\mid x,H_t) u ∼ q ϕ ( ⋅ ∣ x , H t ) is improving from x x x if F ~ ( Apply ( x , u ) ) > F ~ ( x ) \widetilde{F}(\operatorname{Apply}(x,u))>\widetilde{F}(x) F ( Apply ( x , u )) > F ( x ) .
Assumption 1 is stated in the main text (p. 7).
Assumption 1 is a minimum-competence condition : whenever a sufficient improvement is available, one is proposed with non-vanishing probability. It is not a property we prove about the LLM. Three clarifications matter, because the form of the statement carries most of what a reader should take from it.
It is required at one tolerance, and only away from the target. Asking for a single p ⋆ p^\star p ⋆ bounded away from zero at every non-optimal state would not be plausible: near the optimum the remaining gap is small, most single-coordinate edits are neutral or worse, and the improving probability decays toward zero. The assumption avoids that only because ε \varepsilon ε is fixed in advance. Were it required for every ε > 0 \varepsilon>0 ε > 0 , it would reinstate the implausible version: any non-optimal state lies in the sublevel set at ε \varepsilon ε equal to its own gap. With ε \varepsilon ε fixed, coverage is invoked only on states at least ε \varepsilon ε from the target, which is all Theorem 3 uses, since it is stated for that ε \varepsilon ε ; the convergence rate rests on the scored analogue, Assumption 5, in the same form. The decay then shows up as a comparison across instantiations: a practitioner who demands a closer solution assumes coverage at a smaller ε \varepsilon ε , which is a weaker landscape and a larger step requirement in Theorem 4. That is the graceful degradation familiar from stochastic local search, and Section F.4.1 shows the improving rate falling as the leader climbs.
It constrains the landscape, the sampler and the scoring noise jointly. Three things must hold for p ∗ ( ε ) > 0 p^*(\varepsilon)>0 p ∗ ( ε ) > 0 . The state must have an improving single-coordinate neighbor; at a radius-one local maximum that is still ε \varepsilon ε -suboptimal it does not, and block interactions (a single edit fails while a coordinated pair improves) are exactly the mechanism producing such states. The proposer must put positive probability on such a neighbor, which Assumption 2 does not give, since it bounds the support of q ϕ q_\phi q ϕ from above rather than below. And because improvement is judged on the scored objective, the neighbor’s validation score must exceed its parent’s, which depends on the realized validation sample as well as on the population gap. The sublevel set is defined by population utility because the reachability argument reasons about which parents are truly suboptimal; the event inside is judged on the score because that is what the selector sees. In particular, p ∗ ( ε ) > 0 p^*(\varepsilon)>0 p ∗ ( ε ) > 0 requires every state with no score-improving neighbor, a maximizer of the validation score over X \mathcal{X} X included, to be ε \varepsilon ε -optimal in population, so the assumption also asserts that validation overfitting at the score maxima is below ε \varepsilon ε .
Coverage is needed at every parent, not just one. The reachability bound multiplies failure probabilities across all ∣ C t − 1 ∣ k \lvert C_{t-1}\rvert k ∣ C t − 1 ∣ k draws, and each factor is at most 1 − p ∗ ( ε ) 1-p^*(\varepsilon) 1 − p ∗ ( ε ) only if the parent it was drawn from is itself ε \varepsilon ε -suboptimal. That is why Lemma 5 asks it of every parent. If some parent is already ε \varepsilon ε -optimal the hypothesis fails and the theorem says nothing, though the beam then holds an ε \varepsilon ε -optimal candidate, which may not be the leader. Section F.4.1 estimates the improving rate directly from the per-step proposal acceptance rate.
Which results depend on coverage. Coverage, in its population form (Assumption 1) and its scored form (Assumption 5, stated with the convergence rate), is the assumption in this section we cannot verify, so it matters exactly where it is used: the population form in reachability and the scored form in the convergence results, all of which bound a rate. Table 6 makes the dependency structure explicit. The main consequence is that everything that holds by construction is coverage-free: the returned prompt never scores below the seed on the validation split, the beam keeps a competitive distinct-parent candidate whenever one is proposed, and the text of frozen blocks is byte-identical to the seed’s, whether or not the proposer is competent. When coverage fails, SPLICE makes no progress and returns its monotone best-so-far. Coverage failure costs speed, not these guarantees. None of them says that the target obeys a frozen clause; that is behavior, which Section F.2 measures.
Coverage is also not a convenience specific to SPLICE. It is a condition on the problem class: if no improving edit can be proposed from a reachable non-optimal state, no proposer–critic loop can progress from it, so the limitation belongs to the paradigm rather than to our analysis of it. Prior work does carry formal guarantees: ProTeGi’s candidate selection is a bandit procedure, C A P O c o s t \mathrm{CAPO}_{\mathrm{cost}} CAPO cost ’s survival step uses racing with a multiple-testing correction, and constrained variants prove compliance results under their own assumptions. These guarantees concern selecting among candidates, not the trajectory of the search that produced them, so they do not need a condition on what the proposer can generate. We name that condition and measure it.
Theorem 3 is stated in the main text (p. 7).
The bound is on the draws, before deduplication. An improving draw whose child duplicates a member of C t − 1 C_{t-1} C t − 1 , or an earlier draw of the step, is removed from N t \mathcal{N}_t N t ; the state it reached is then already in the beam or in N t \mathcal{N}_t N t , so it adds no new candidate.
The exponent counts the draws made, ∣ C t − 1 ∣ k \lvert C_{t-1}\rvert k ∣ C t − 1 ∣ k , and not the budget W k Wk W k ; the two coincide only once the beam is full. They do coincide for the whole run after the first step whenever 1 + k ≥ W 1+k\ge W 1 + k ≥ W , as at W = 4 W=4 W = 4 with k = 3 k=3 k = 3 (GPQA and the seeded SST-5 sweeps) or k = 5 k=5 k = 5 (BBH), since the step-1 frontier holds 1 + k ≥ W 1+k\ge W 1 + k ≥ W candidates and elitist selection retains W W W of them, so ∣ C t − 1 ∣ = W \lvert C_{t-1}\rvert=W ∣ C t − 1 ∣ = W for every t ≥ 2 t\ge2 t ≥ 2 whenever the frontier supplies W W W distinct candidates and, when ρ > 0 \rho>0 ρ > 0 , at least D D D non-elite frontier members clear the quality gate (automatic for ρ = 0 \rho=0 ρ = 0 , as on GPQA and BBH). At t = 1 t=1 t = 1 the exponent is k k k , because C 0 = { x ( 0 ) } C_0=\{x^{(0)}\} C 0 = { x ( 0 ) } is a single parent. We state the theorem in the exact form rather than the budgeted one because substituting W k Wk W k at t = 1 t=1 t = 1 would overstate the first step’s guarantee, and the first step is where the run has the least to fall back on.
Theorem 3 quantifies the joint effect of beam width and proposals-per-candidate: increasing either drives the failure probability to zero exponentially. It is a statement about some parent improving, and it is the wrong quantity for predicting whether the search makes progress. At W k = 12 Wk = 12 W k = 12 a per-proposal rate of 0.25 0.25 0.25 gives p s t e p = 0.97 p^{\mathrm{step}} = 0.97 p step = 0.97 and even 0.08 0.08 0.08 gives 0.63 0.63 0.63 , so by this measure fan-out looks almost freely substitutable for proposer quality. Progress of the leader , which is what Theorem 4 counts, runs on the leader’s own k k k draws, and there the same rates give 0.58 0.58 0.58 and 0.22 0.22 0.22 at k = 3 k = 3 k = 3 . So the operating condition is p ⋆ ( ε ) p^{\star}(\varepsilon) p ⋆ ( ε ) above 1 / k 1/k 1/ k , not 1 / W k 1/Wk 1/ W k , and beam width buys reachability without buying the proven rate. The coverage rate is also not a property of the proposer alone: Section F.4.1 measures it with the proposer fixed and finds it rises with the capacity of the target model, so where a given proposer falls relative to that condition depends on what it is prompting.
Proofs
Proof of Proposition 3. Fix x = ( v , π ) x = (v, \pi) x = ( v , π ) and x ′ = ( v ′ , π ′ ) x' = (v', \pi') x ′ = ( v ′ , π ′ ) in X \mathcal{X} X , where v , v ′ v, v' v , v ′ are the block-variant assignments and π , π ′ \pi, \pi' π , π ′ the orderings. We exhibit a path in the edit graph of the stated length.
A block-replacement move alters one coordinate v i v_i v i and leaves π \pi π fixed; an ordering move alters π \pi π and leaves every v i v_i v i fixed. The two families therefore act on disjoint coordinates of the pair ( v , π ) (v, \pi) ( v , π ) and commute as operators on X \mathcal{X} X , so we may schedule all replacements before all ordering moves without changing the endpoint.
Replacement phase. For each i i i with v i ≠ v i ′ v_i \ne v_i' v i = v i ′ , one block-replacement move sends v i ↦ v i ′ v_i \mapsto v_i' v i ↦ v i ′ ; this is admissible because v i ′ ∈ V i v_i' \in\mathcal{V}_i v i ′ ∈ V i by x ′ ∈ X x' \in\mathcal{X} x ′ ∈ X . Immutable blocks satisfy v i = v i ( 0 ) = v i ′ v_i = v_i^{(0)} = v_i' v i = v i ( 0 ) = v i ′ by Definition 3 and so contribute no move. A block with ∣ V i ∣ = 1 |\mathcal{V}_i| = 1 ∣ V i ∣ = 1 likewise cannot differ. Hence the number of replacement moves is at most ∑ i ∈ I m u t 1 { ∣ V i ∣ ≥ 2 } ≤ m m u t \sum_{i \in I_{\mathrm{mut}}} 1\{|\mathcal{V}_i| \ge2\} \le m_{\mathrm{mut}} ∑ i ∈ I mut 1 { ∣ V i ∣ ≥ 2 } ≤ m mut .
Ordering phase. The reachable orderings form the connected set Π \Pi Π under the admissible ordering moves, so π \pi π and π ′ \pi' π ′ are joined by at most diam ( Π ) \operatorname{diam}(\Pi) diam ( Π ) such moves.
Concatenating the two phases gives a path of length at most m m u t + diam ( Π ) m_{\mathrm{mut}} + \operatorname{diam}(\Pi) m mut + diam ( Π ) , and since x , x ′ x, x' x , x ′ were arbitrary this bounds the diameter, which is (10). Selective mutability enters only through the replacement phase: freezing block i i i removes it from I m u t I_{\mathrm{mut}} I mut and hence deletes one unit from the bound.
The exponent in Theorem 3 counts every draw made in the expansion, ∣ C t − 1 ∣ k |\mathcal{C}_{t-1}|\,k ∣ C t − 1 ∣ k , and each draw only carries the coverage guarantee if the parent it was drawn from is itself ε \varepsilon ε -suboptimal. We isolate that condition first.
Lemma 5 (When every parent carries the coverage guarantee). Suppose max x ∈ C t − 1 F ⋆ ( x ) ≤ F ⋆ ( x ⋆ ) − ε \max_{x \in\mathcal{C}_{t-1}} F^{\star}(x) \le F^{\star}(x^{\star}) - \varepsilon max x ∈ C t − 1 F ⋆ ( x ) ≤ F ⋆ ( x ⋆ ) − ε , i.e. the beam contains no ε \varepsilon ε -optimal candidate. Then every x ∈ C t − 1 x \in\mathcal{C}_{t-1} x ∈ C t − 1 lies in the ε \varepsilon ε -sublevel set of Assumption 1, and hence every draw u ∼ q ϕ ( ⋅ ∣ x , H t ) u \sim q_{\phi}(\cdot\mid x, H_t) u ∼ q ϕ ( ⋅ ∣ x , H t ) from every parent is improving from its parent with probability at least p ⋆ ( ε ) p^{\star}(\varepsilon) p ⋆ ( ε ) .
Proof. Immediate: if the maximum population utility over the beam is at most F ⋆ ( x ⋆ ) − ε F^{\star}(x^{\star}) - \varepsilon F ⋆ ( x ⋆ ) − ε then each individual member satisfies F ⋆ ( x ⋆ ) − F ⋆ ( x ) ≥ ε F^{\star}(x^{\star}) - F^{\star}(x) \ge\varepsilon F ⋆ ( x ⋆ ) − F ⋆ ( x ) ≥ ε , which is precisely the constraint indexing the minimum in Assumption 1.
Proof of Theorem 3. Condition on C t − 1 \mathcal{C}_{t-1} C t − 1 and the history H t H_t H t , and assume the hypothesis of Lemma 5. Index the draws of the expansion by ( x , j ) (x,j) ( x , j ) with x ∈ C t − 1 x \in\mathcal{C}_{t-1} x ∈ C t − 1 and j ∈ [ k ] j \in[k] j ∈ [ k ] , so there are ∣ C t − 1 ∣ ⋅ k ≤ W k |\mathcal{C}_{t-1}| \cdot k \le Wk ∣ C t − 1 ∣ ⋅ k ≤ W k of them.
Independence. Within a parent, the k k k draws are i.i.d. from q ϕ ( ⋅ ∣ x , H t ) q_\phi(\cdot\mid x,H_t) q ϕ ( ⋅ ∣ x , H t ) by (6). Across parents, each parent’s expansion is a separate invocation of the proposer with its own randomness, and all of them condition on the same fixed ( C t − 1 , H t ) (\mathcal{C}_{t-1},H_t) ( C t − 1 , H t ) ; hence the full collection { u x , j } \{u_{x,j}\} { u x , j } is mutually independent given ( C t − 1 , H t ) (\mathcal{C}_{t-1},H_t) ( C t − 1 , H t ) .
Failure probability. Let A x , j A_{x,j} A x , j be the event that u x , j u_{x,j} u x , j is improving from x x x in the sense of Definition 15. By Lemma 5, Pr [ A x , j ] ≥ p ⋆ ( ε ) \Pr[A_{x,j}] \ge p^\star(\varepsilon) Pr [ A x , j ] ≥ p ⋆ ( ε ) for every ( x , j ) (x,j) ( x , j ) . The event that the expansion contains no improving child is ⋂ x , j A x , j c \bigcap_{x,j} A_{x,j}^{c} ⋂ x , j A x , j c , and by independence
Pr [ ⋂ x , j A x , j c ] = ∏ x , j Pr [ A x , j c ] ≤ ( 1 − p ⋆ ( ε ) ) ∣ C t − 1 ∣ k . \Pr\left[\bigcap_{x,j} A_{x,j}^{c}\right] = \prod_{x,j}\Pr[A_{x,j}^{c}] \le\left(1-p^\star(\varepsilon)\right)^{|\mathcal{C}_{t-1}|k}. Pr [ x , j ⋂ A x , j c ] = x , j ∏ Pr [ A x , j c ] ≤ ( 1 − p ⋆ ( ε ) ) ∣ C t − 1 ∣ k .
Taking complements gives Theorem 3. Feasibility of every draw (no proposal leaves X \mathcal{X} X or writes to an immutable block) is Assumption 2, so every improving draw reaches a state of X \mathcal{X} X . The event is on the draws { u x , j } \{u_{x,j}\} { u x , j } , not on N t \mathcal{N}_t N t after deduplication: a draw whose child duplicates a member of C t − 1 \mathcal{C}_{t-1} C t − 1 or an earlier draw is removed, and the state it reached is already in the beam or in N t \mathcal{N}_t N t .
One tempting step is unavailable, although the budgeted form reads like a harmless simplification. Bounding ( 1 − p ⋆ ) ∣ C t − 1 ∣ k (1-p^\star)^{|\mathcal{C}_{t-1}|k} ( 1 − p ⋆ ) ∣ C t − 1 ∣ k above by ( 1 − p ⋆ ) W k (1-p^\star)^{Wk} ( 1 − p ⋆ ) W k does not follow from ∣ C t − 1 ∣ ≤ W |\mathcal{C}_{t-1}| \le W ∣ C t − 1 ∣ ≤ W : because 0 ≤ 1 − p ⋆ ≤ 1 0 \le1-p^\star\le1 0 ≤ 1 − p ⋆ ≤ 1 , raising it to the larger exponent makes it smaller , so ( 1 − p ⋆ ) W k ≤ ( 1 − p ⋆ ) ∣ C t − 1 ∣ k (1-p^\star)^{Wk} \le(1-p^\star)^{|\mathcal{C}_{t-1}|k} ( 1 − p ⋆ ) W k ≤ ( 1 − p ⋆ ) ∣ C t − 1 ∣ k and the substitution runs the wrong way. The budgeted form is therefore a valid bound only when the beam is full. It fails at t = 1 t=1 t = 1 , where ∣ C 0 ∣ = 1 |\mathcal{C}_0|=1 ∣ C 0 ∣ = 1 , and the exponent is k k k .
Approximate Submodularity and Greedy Approximation
Theorem 3 bounds the probability that some proposal improves on its parent, which need not move the leader, but is silent about how much progress is possible overall. A terminal-quality bound needs structural information about F ⋆ F^\star F ⋆ . We import the standard framework: approximate submodularity of the utility as a set function over block-variant commits. Fixing π = π ( 0 ) \pi=\pi^{(0)} π = π ( 0 ) , let
E = { ( i , v ) : i ∈ I m u t , v ∈ V i ∖ { v i ( 0 ) } } , E a l l = { ( i , v ) : i ∈ [ m ] , v ∈ V ~ i ∖ { v i ( 0 ) } } . (13) E = \{(i,v): i\in I_{\mathrm{mut}},\ v\in V_i\setminus\{v_i^{(0)}\}\}, \qquad E^{\mathrm{all}} = \{(i,v): i\in[m],\ v\in\widetilde{V}_i\setminus\{v_i^{(0)}\}\}. \tag*{(13)} E = {( i , v ) : i ∈ I mut , v ∈ V i ∖ { v i ( 0 ) }} , E all = {( i , v ) : i ∈ [ m ] , v ∈ V i ∖ { v i ( 0 ) }} . (13)
where V ~ i \widetilde{V}_i V i denotes the counterfactual variant set of block i i i (the variants block i i i would admit had it not been frozen), with v i ( 0 ) ∈ V ~ i v_i^{(0)}\in\widetilde{V}_i v i ( 0 ) ∈ V i for every i i i and V ~ i = V i \widetilde{V}_i=V_i V i = V i for every i ∈ I m u t i\in I_{\mathrm{mut}} i ∈ I mut , so that X a l l = ( ∏ i V ~ i ) × Π \mathcal{X}_{\mathrm{all}}=\left(\prod_i\widetilde{V}_i\right)\times\Pi X all = ( ∏ i V i ) × Π . So E E E collects the alternative variants across mutable blocks, each tagged with its block so that equal text in two blocks gives two elements, and E a l l ⊇ E E^{\mathrm{all}}\supseteq E E all ⊇ E additionally carries the alternatives that freezing removed. Call A ⊆ E a l l A\subseteq E^{\mathrm{all}} A ⊆ E all feasible if it has at most one entry per block, and for feasible A A A let x A x_A x A substitute each ( i , v ) ∈ A (i,v)\in A ( i , v ) ∈ A into x ( 0 ) x^{(0)} x ( 0 ) . The gain function, defined on feasible sets, is
g ( A ) : = F ⋆ ( x A ) − F ⋆ ( x ( 0 ) ) , g ( ∅ ) = 0. (14) g(A) := F^\star(x_A)-F^\star(x^{(0)}), \qquad g(\varnothing)=0. \tag*{(14)} g ( A ) := F ⋆ ( x A ) − F ⋆ ( x ( 0 ) ) , g ( ∅ ) = 0. (14)
well defined on every feasible subset of E a l l E^{\mathrm{all}} E all because (2) depends on a state only through render ( x ) \operatorname{render}(x) render ( x ) and so extends verbatim from X \mathcal{X} X to the all-mutable space X a l l \mathcal{X}_{\mathrm{all}} X all of (5). Prompt optimization over mutable blocks is constrained maximization of g g g on E E E ; the larger ground set enters only in Proposition 2, to express what the restriction to E E E costs.
Two points about V ~ i \widetilde{V}_i V i , since it is the one object here not already supplied by Section 2. First, it is what makes the price of freezing expressible at all. By Definition 3 an immutable block has V i = { v i ( 0 ) } V_i=\{v_i^{(0)}\} V i = { v i ( 0 ) } , so any quantity written as a maximum over V i V_i V i for i ∈ I i m m i\in I_{\mathrm{imm}} i ∈ I imm is identically zero, and a bound in that form could only ever assert that freezing is free. The counterfactual set is the smallest addition that lets the question be posed. Second, it is not observable : recovering V ~ i \widetilde{V}_i V i would mean running the search with the contract released, which is precisely what deployment forbids. E a l l E^{\mathrm{all}} E all therefore buys a meaningful statement, not a measurable one (Remark 14). Search itself never touches E a l l ∖ E E^{\mathrm{all}}\setminus E E all ∖ E : every algorithm in this paper optimizes g g g over E E E alone.
We note the shape of the constraint on E E E now, because it matters for what the approximation guarantee below covers: the feasible sets are those with at most one entry per block, which form a partition matroid with one part per mutable block and capacity one, not a cardinality constraint.
Definition 16 (Submodularity ratio, 16). The submodularity ratio of g g g on a ground set E ′ E' E ′ is
γ ( g ; E ′ ) : = min L , S ⊆ E ′ , L ∩ S = ∅ L ∪ S feasible , g ( L ∪ S ) > g ( L ) ∑ e ∈ S [ g ( L ∪ { e } ) − g ( L ) ] g ( L ∪ S ) − g ( L ) ≤ 1 , (15) \gamma(g;E') := \min_{\substack{L,S\subseteq E',\ L\cap S=\varnothing\\ L\cup S\ \text{feasible},\ g(L\cup S)>g(L)}} \frac{\sum_{e\in S}[g(L\cup\{e\})-g(L)]}{g(L\cup S)-g(L)} \le1, \tag*{(15)} γ ( g ; E ′ ) := L , S ⊆ E ′ , L ∩ S = ∅ L ∪ S feasible , g ( L ∪ S ) > g ( L ) min g ( L ∪ S ) − g ( L ) ∑ e ∈ S [ g ( L ∪ { e }) − g ( L )] ≤ 1 , (15) the minimum running over the pairs on which g g g is defined. It is the ratio of Das and Kempe [16 ] restricted to the partition matroid; when every subset is feasible the two coincide. γ = 1 \gamma=1 γ = 1 recovers standard submodularity; γ = 0 \gamma=0 γ = 0 indicates fully complementary interactions.
Assumption 4 (γ \gamma γ -submodular utility). The gain function g g g of (14) has submodularity ratio γ ( g ; E a l l ) ≥ γ \gamma(g;E^{\mathrm{all}})\ge\gamma γ ( g ; E all ) ≥ γ for some γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] .
We state Assumption 4 on the larger ground set because Proposition 2 compares across the frozen/unfrozen boundary and so needs γ \gamma γ to control marginals on frozen coordinates too. Nothing is lost for the results that live on E E E : since E ⊆ E a l l E\subseteq E^{\mathrm{all}} E ⊆ E all , the minimum in (15) runs over at least as many pairs on the larger set, so γ ( g ; E a l l ) ≤ γ ( g ; E ) \gamma(g;E^{\mathrm{all}})\le\gamma(g;E) γ ( g ; E all ) ≤ γ ( g ; E ) and the assumption implies γ ( g ; E ) ≥ γ \gamma(g;E)\ge\gamma γ ( g ; E ) ≥ γ . Proposition 4 and Conjecture 1 may therefore be read with γ \gamma γ on E E E . The cost of the stronger form is that γ \gamma γ becomes a property of a landscape that includes unobservable coordinates. We report no estimate of γ \gamma γ on either ground set: estimating it per benchmark would take block-subset ablations we have not run, and it remains open (§ 6 ).
Beyond its scope, Assumption 4 is a structural assumption on the task, not the algorithm: block interactions are bounded. It does not assert monotonicity, that no block-level commit lowers utility. That would rarely hold on the whole ground set when V i V_i V i holds every admissible text (Definition 2), and only Proposition 4 asks for it, on E E E and in the single-alternative regime.
The shape of the constraint decides what is provable, and the two regimes it admits behave very differently. When each mutable block has a single alternative to its seed text, every subset of E E E is feasible and the partition constraint does no work. This regime is an idealization: by Definition 2, V i V_i V i holds every variant the proposer could produce, so no run of SPLICE is in it. We analyze it because it isolates what γ > 0 \gamma>0 γ > 0 buys, for an idealized greedy that sees the exact gain function. Block-pass greedy starts from A 0 = ∅ A_0=\varnothing A 0 = ∅ ; at each pass it evaluates g ( A j ∪ { e } ) g(A_j\cup\{e\}) g ( A j ∪ { e }) for every remaining e ∈ E e\in E e ∈ E , commits the element with the largest positive marginal gain, and stops when no marginal is positive. In this regime the guarantee is not an approximation factor but an exact one.
Proposition 4 (Block-pass greedy is exact in the single-alternative regime). Suppose each mutable block contributes exactly one alternative, so that E = { ( i , v ~ i ) : i ∈ I m u t } E=\{(i,\tilde v_i):i\in I_{\mathrm{mut}}\} E = {( i , v ~ i ) : i ∈ I mut } and every subset of E E E is feasible, and that g g g is monotone non-decreasing on E E E (g ( A ) ≤ g ( A ′ ) g(A)\le g(A') g ( A ) ≤ g ( A ′ ) whenever A ⊆ A ′ ⊆ E A\subseteq A'\subseteq E A ⊆ A ′ ⊆ E ). Under Assumption 4, block-pass greedy returns a commit set A g r A_{\mathrm{gr}} A gr with
g ( A g r ) = max A ⊆ E g ( A ) , (16) g(A_{\mathrm{gr}})=\max_{A\subseteq E}g(A), \tag*{(16)} g ( A gr ) = A ⊆ E max g ( A ) , (16) that is, x A g r x_{A_{\mathrm{gr}}} x A gr attains the best utility reachable by block replacement at the baseline ordering.
Two things follow, and the second is a limitation. First, in this regime a positive submodularity ratio is doing more work than an approximation guarantee would suggest: γ > 0 \gamma>0 γ > 0 forbids exactly the configuration that traps greedy, a set of blocks that is valuable jointly while each of its members is worthless alone. Second, the regime is narrow. As soon as some block offers two or more alternatives the feasible sets form a non-trivial partition matroid , greedy must also choose which variant to commit per block, and no terminal-quality guarantee we are aware of covers deterministic block-pass greedy there: the best available result for monotone γ \gamma γ -weakly-submodular maximization under a matroid constraint is ( 1 + 1 / γ ) − 2 (1+1/\gamma)^{-2} ( 1 + 1/ γ ) − 2 for a randomized greedy variant [10 ] , and whether deterministic greedy attains any non-trivial ratio beyond cardinality constraints was open in that work. Remark 4 records what this does and does not justify. We therefore claim no approximation factor in the multi-alternative regime rather than import one that does not apply.
Wider beams maintain multiple partial configurations and can commit to coordinated multi-block edits greedy would reject. Since Proposition 4 leaves nothing to improve when a single alternative per block is on offer, the interesting claim lives in the multi-alternative regime:
Conjecture 1 (Beam improvement). In the multi-alternative regime, fix γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] and a proposer that puts positive probability on every feasible single-block edit, score with the exact gain g g g , and run elitist beam search of width W W W until no proposal can improve a beam member. Let α γ ( W ) \alpha_\gamma(W) α γ ( W ) be the worst case, over instances whose submodularity ratio is at least γ \gamma γ , of the expected ratio between the returned leader’s gain and max A g ( A ) \max_A g(A) max A g ( A ) over feasible A A A . Then α γ \alpha_\gamma α γ is non-decreasing in W W W , and, over the instances where some optimal commit set requires two or more blocks to move together, strictly increasing for W ≤ m m u t W \le m_{\mathrm{mut}} W ≤ m mut .
We state Conjecture 1 as a conjecture, and deliberately in qualitative form. A proof would require a coupling between the beam’s W W W lineages that elitist selection makes dependent, so the product-of-failure-probabilities argument does not apply; and we do not conjecture a specific functional form for α γ \alpha_\gamma α γ , because no deterministic-greedy baseline exists in this regime (Proposition 4) for such a form to interpolate from. What is provable is a pathwise comparison:
Proposition 5 (Elitist beam stays ahead of greedy until they separate). Run elitist beam search, with selector S e l i t - d i v S_{\mathrm{elit\text{-}div}} S elit - div for any D ≤ W − 1 D \le W-1 D ≤ W − 1 (which includes SPLICE), and greedy on the same proposal draws, with scores cached per state and shared by both runs: whenever greedy’s state x t g x_t^{\mathrm{g}} x t g lies in C t C_t C t , both procedures see the same k k k children of it. Let ν : = min { t : x t g ∉ C t } \nu:= \min\{t : x_t^{\mathrm{g}} \notin C_t\} ν := min { t : x t g ∈ / C t } , with ν = ∞ \nu= \infty ν = ∞ if no such step exists. Then
ℓ t ≥ F ~ ( x min ( t , ν ) g ) \ell_t \ge\widetilde{F}\left(x_{\min(t,\nu)}^{\mathrm{g}}\right) ℓ t ≥ F ( x m i n ( t , ν ) g ) for every t ≤ T t \le T t ≤ T .
For W = 1 W = 1 W = 1 the two procedures coincide under a common tie-breaking rule, so ν = ∞ \nu= \infty ν = ∞ and ℓ t = F ~ ( x t g ) \ell_t = \widetilde{F}(x_t^{\mathrm{g}}) ℓ t = F ( x t g ) for every t t t .
Here greedy is hill climbing with retention: it moves to its best child only if that child scores at least as high as its current state. The Greedy arm of Section 4 is the children-only beam with W = 1 W=1 W = 1 of Section C.1, which can regress, so Proposition 5 does not describe it.
The comparison stops at ν \nu ν because greedy then proposes from a state the beam no longer holds, and the beam never scores those children; Remark 5 gives a three-step instance with W = 2 W=2 W = 2 in which greedy finishes above the beam leader. The domination is also on the scored objective F ~ \widetilde{F} F that both selectors act on, since a score ordering need not agree with the population ordering, and it needs the coupling: two runs with independent draws cannot be compared path by path.
Proposition 5 says that an elitist beam is never behind the greedy path while it holds that path, and is at least level with greedy at the step it drops it. It does not say the beam finishes ahead of greedy; Conjecture 1 is the empirically motivated claim that the benefit scales with W W W .
Proofs. The feasible sets of (14) are the subsets of E = { ( i , v ) : i ∈ I m u t , v ∈ V i ∖ { v i ( 0 ) } } E = \{(i,v) : i \in I_{\mathrm{mut}},\ v \in\mathcal{V}_i \setminus\{v_i^{(0)}\}\} E = {( i , v ) : i ∈ I mut , v ∈ V i ∖ { v i ( 0 ) }} containing at most one element per block. These form a partition matroid with one part per mutable block and capacity one, which is not a cardinality constraint. The distinction collapses in one regime and bites in the other, and the two need separating before either can be argued. When every mutable block offers exactly one alternative, each part contributes one element, every subset is feasible, and the rank budget m m u t m_{\mathrm{mut}} m mut is non-binding; otherwise the matroid constraint is non-trivial. Proposition 4 covers the first case and Remark 4 states what is and is not known about the second.
uses only γ > 0 \gamma> 0 γ > 0 and monotonicity and needs no external approximation theorem. The reduction also does not extend: it compares greedy against the best subset of E ^ \hat{E} E ^ rather than against the optimum over E E E , and those differ as soon as a block offers a second alternative, which is the regime Remark 4 addresses.
Proof of Proposition 4. By hypothesis E = { ( i , v ^ i ) : i ∈ I m u t } E = \{(i, \hat{v}_i) : i \in I_{\mathrm{mut}}\} E = {( i , v ^ i ) : i ∈ I mut } carries exactly one element per part, so every subset of E E E is feasible and the cardinality budget m m u t = ∣ E ∣ m_{\mathrm{mut}} = |E| m mut = ∣ E ∣ is non-binding. Let A g r A_{\mathrm{gr}} A gr be greedy’s output. Greedy halts only when no remaining element has positive marginal gain, so g ( A g r ∪ { e } ) − g ( A g r ) ≤ 0 g(A_{\mathrm{gr}} \cup\{e\}) - g(A_{\mathrm{gr}}) \le0 g ( A gr ∪ { e }) − g ( A gr ) ≤ 0 for every e ∈ E ∖ A g r e \in E \setminus A_{\mathrm{gr}} e ∈ E ∖ A gr ; by the monotonicity hypothesis of Proposition 4 each such marginal is also non-negative, hence
g ( A g r ∪ { e } ) − g ( A g r ) = 0 for all e ∈ E ∖ A g r . (17) g(A_{\mathrm{gr}} \cup\{e\}) - g(A_{\mathrm{gr}}) = 0 \qquad\text{for all } e \in E \setminus A_{\mathrm{gr}}. \tag*{(17)} g ( A gr ∪ { e }) − g ( A gr ) = 0 for all e ∈ E ∖ A gr . (17)
Suppose for contradiction that g ( E ) > g ( A g r ) g(E) > g(A_{\mathrm{gr}}) g ( E ) > g ( A gr ) . Then L : = A g r L := A_{\mathrm{gr}} L := A gr and S : = E ∖ A g r S := E \setminus A_{\mathrm{gr}} S := E ∖ A gr are disjoint with g ( L ∪ S ) = g ( E ) > g ( L ) g(L \cup S) = g(E) > g(L) g ( L ∪ S ) = g ( E ) > g ( L ) , so ( L , S ) (L,S) ( L , S ) is admissible in the minimum defining γ ( g ; E ) \gamma(g;E) γ ( g ; E ) in (15), and that definition gives
γ [ g ( E ) − g ( A g r ) ] ≤ ∑ e ∈ E ∖ A g r [ g ( A g r ∪ { e } ) − g ( A g r ) ] = 0 \gamma[g(E) - g(A_{\mathrm{gr}})] \le\sum_{e \in E \setminus A_{\mathrm{gr}}} [g(A_{\mathrm{gr}} \cup\{e\}) - g(A_{\mathrm{gr}})] = 0 γ [ g ( E ) − g ( A gr )] ≤ e ∈ E ∖ A gr ∑ [ g ( A gr ∪ { e }) − g ( A gr )] = 0
by (18). Since γ > 0 \gamma> 0 γ > 0 this forces g ( E ) ≤ g ( A g r ) g(E) \le g(A_{\mathrm{gr}}) g ( E ) ≤ g ( A gr ) , contradicting the supposition. Hence g ( A g r ) = g ( E ) g(A_{\mathrm{gr}}) = g(E) g ( A gr ) = g ( E ) , and g ( E ) ≥ g ( A ) g(E) \ge g(A) g ( E ) ≥ g ( A ) for every A ⊆ E A \subseteq E A ⊆ E by monotonicity, so g ( A g r ) = max A ⊆ E g ( A ) g(A_{\mathrm{gr}}) = \max_{A \subseteq E} g(A) g ( A gr ) = max A ⊆ E g ( A ) ; with g ( A ) = F ⋆ ( x A ) − F ⋆ ( x ( 0 ) ) g(A) = F^{\star}(x_A) - F^{\star}(x^{(0)}) g ( A ) = F ⋆ ( x A ) − F ⋆ ( x ( 0 ) ) from (14) this is (16).
The hypothesis γ > 0 \gamma> 0 γ > 0 is needed here for the conclusion to hold, not only to bound its loss: it rules out a set of blocks that is jointly valuable while each member is individually worthless, which is the only configuration that could strand greedy at a zero-marginal set. The conclusion fails at γ = 0 \gamma= 0 γ = 0 . Take two blocks with g ( ∅ ) = g ( { a } ) = g ( { b } ) = 0 g(\varnothing) = g(\{a\}) = g(\{b\}) = 0 g ( ∅ ) = g ({ a }) = g ({ b }) = 0 and g ( { a , b } ) = 1 g(\{a,b\}) = 1 g ({ a , b }) = 1 : this is monotone with γ ( g ; E ) = 0 \gamma(g;E) = 0 γ ( g ; E ) = 0 , greedy halts immediately and returns 0, and the optimum is 1.
Proof of Proposition 5. The claim is a statement about two algorithms run on shared randomness, so we first fix the coupling it is made under. At every step, the k k k draws greedy makes from its current state x t g x_t^{g} x t g are the same k k k draws the beam makes from x t g x_t^{g} x t g whenever x t g ∈ C t x_t^{g} \in C_t x t g ∈ C t . Scores are the cached validation scores F ~ ( ⋅ ; D v a l i d ) \tilde{F}(\cdot; \mathcal{D}_{\mathrm{valid}}) F ~ ( ⋅ ; D valid ) of Section 2, cached per state and shared by the coupled runs, so a given state carries the same score in both. Since C 0 = { x ( 0 ) } = { x 0 g } C_0 = \{x^{(0)}\} = \{x_0^g\} C 0 = { x ( 0 ) } = { x 0 g } , ν ≥ 1 \nu\ge1 ν ≥ 1 .
Steps t < ν t < \nu t < ν . By definition of ν \nu ν , x t g ∈ C t x_t^g \in C_t x t g ∈ C t , so ℓ t = max x ∈ C t F ~ ( x ) ≥ F ~ ( x t g ) \ell_t = \max_{x \in C_t} \tilde{F}(x) \ge\tilde{F}(x_t^g) ℓ t = max x ∈ C t F ~ ( x ) ≥ F ~ ( x t g ) . Step t = ν < ∞ t = \nu< \infty t = ν < ∞ . Since x ν − 1 g ∈ C ν − 1 x^{g}_{\nu-1} \in C_{\nu-1} x ν − 1 g ∈ C ν − 1 , the coupling puts greedy’s k k k children of x ν − 1 g x^{g}_{\nu-1} x ν − 1 g into the beam’s expansion, or into C ν − 1 C_{\nu-1} C ν − 1 if deduplication removed them as duplicates of beam members. Greedy’s next state is either one of these children or x ν − 1 g x^{g}_{\nu-1} x ν − 1 g itself, so in every case x ν g ∈ F ν = C ν − 1 ∪ N ν x^{g}_{\nu} \in F_{\nu} = C_{\nu-1} \cup N_{\nu} x ν g ∈ F ν = C ν − 1 ∪ N ν . Elitist selection retains the top W − D ≥ 1 W - D \ge1 W − D ≥ 1 members of F ν F_{\nu} F ν by score, and x ν g x^{g}_{\nu} x ν g is not retained, so every retained elite scores at least F ~ ( x ν g ) \widetilde{F}(x^{g}_{\nu}) F ( x ν g ) ; in particular ℓ ν ≥ F ~ ( x ν g ) \ell_{\nu} \ge\widetilde{F}(x^{g}_{\nu}) ℓ ν ≥ F ( x ν g ) .
Steps t > ν t > \nu t > ν . By Lemma 1, ℓ t ≥ ℓ ν ≥ F ~ ( x ν g ) = F ~ ( x min ( t , ν ) g ) \ell_t \ge\ell_{\nu} \ge\widetilde{F}(x^{g}_{\nu}) = \widetilde{F}(x^{g}_{\min(t,\nu)}) ℓ t ≥ ℓ ν ≥ F ( x ν g ) = F ( x m i n ( t , ν ) g ) .
For W = 1 W = 1 W = 1 , D = 0 D = 0 D = 0 and C t C_t C t is the single highest-scoring member of { x } ∪ { children of x } \{x\} \cup\{\text{children of } x\} { x } ∪ { children of x } for the current state x x x , which is greedy’s rule; with a common tie-breaking rule the two runs visit the same states, so x t g ∈ C t x^{g}_t \in C_t x t g ∈ C t for all t t t and ν = ∞ \nu= \infty ν = ∞ .
Remark 5 (The comparison cannot extend past ν \nu ν . ) After displacement greedy draws from a state the beam no longer holds, so its children are never scored by the beam and elitism cannot retain them. Take W = 2 W = 2 W = 2 , D = 0 D = 0 D = 0 , k = 2 k = 2 k = 2 and cached scores. At t = 1 t = 1 t = 1 the seed (0.50) has children scoring 0.60 and 0.40; greedy moves to the 0.60 child and the beam keeps it and the seed. At t = 2 t = 2 t = 2 the seed draws children scoring 0.90 and 0.85, and the 0.60 state draws 0.61 and 0.30 (shared with greedy); greedy moves to 0.61, and the beam keeps { 0.90 , 0.85 } \{0.90, 0.85\} { 0.90 , 0.85 } , so ν = 2 \nu= 2 ν = 2 . At t = 3 t = 3 t = 3 every child of the beam scores 0.10, while greedy’s own draw from the 0.61 state scores 0.95. Then ℓ 3 = 0.90 < 0.95 \ell_3 = 0.90 < 0.95 ℓ 3 = 0.90 < 0.95 , while (17) requires only ℓ 3 ≥ 0.61 \ell_3 \ge0.61 ℓ 3 ≥ 0.61 . Each step has positive probability under a proposer that conditions on the history, as Definition 13 allows.
Remark 6 (Scored versus population comparison. ) The argument is carried out on the cached score F ~ ( ⋅ ; D v a l i d ) \widetilde{F}(\cdot; \mathcal{D}_{\mathrm{valid}}) F ( ⋅ ; D valid ) , which is the quantity both selectors act on, and it is exact there. The corresponding population statement F ⋆ ( leader ( C t ) ) ≥ F ⋆ ( x min ( t , ν ) g ) F^{\star}(\operatorname{leader}(C_t)) \ge F^{\star}(x^{g}_{\min(t,\nu)}) F ⋆ ( leader ( C t )) ≥ F ⋆ ( x m i n ( t , ν ) g ) does not follow pathwise, because a score ordering need not agree with the population ordering; it holds up to the uniform deviation of Theorem 7, i.e. with 2 ε 2\varepsilon 2 ε slack on the event of that theorem. We state the proposition on the scored objective for this reason.
Remark 7 (Why Conjecture 1 resists this argument. ) The proof above compares the beam with greedy only up to the displacement step ν \nu ν , and says nothing about how the beam’s advantage grows with W W W . Showing that α γ \alpha_{\gamma} α γ grows with W W W would require the W W W lineages to contribute independent progress, and the natural product-of-failure-probabilities argument does not apply: elitist selection couples the lineages, since which candidates survive depends on the scores of all of them jointly, and the reserved diversity slots induce further dependence through the shared quality gate τ t = ρ ℓ t \tau_t = \rho\ell_t τ t = ρ ℓ t . We therefore leave Conjecture 1 as a conjecture and rely on Proposition 5 wherever the comparison is needed.
Elitist Monotonicity and Noisy No-Regression
This subsection characterizes what elitist selection buys over the children-only beam of ProTeGi. Throughout we use SPLICE’s cached-scoring convention stated at the start of this section: each state x x x carries the regularized validation score F ~ ( x ; D v a l i d ) \widetilde{F}(x; \mathcal{D}_{\mathrm{valid}}) F ( x ; D valid ) realized when x x x was first evaluated, not recomputed while it stays in the beam. This avoids the selection-on-noise bias that re-rolling would introduce, and its consequence for monotonicity is direct.
Lemma 1 is stated in the main text (p. 6).
We state Lemma 1 as a lemma rather than a theorem because it is a consequence of the definitions, not a claim about search dynamics. The proof is two lines: C t − 1 ⊆ F t C_{t-1} \subseteq F_t C t − 1 ⊆ F t and scores are cached, so a maximum over a superset of a set whose values have not changed cannot fall. It therefore holds for any elitist selector over any proposal distribution, including an adversarial one. No property of prompt space is used and no experiment can falsify it.
It is nonetheless necessary: cached scoring is a design decision with a real cost, and this lemma justifies it. Later arguments use ℓ t \ell_t ℓ t ’s monotonicity as a hypothesis. The output rule (Section 2) returns leader ( C T ) \operatorname{leader}(C_T) leader ( C T ) , and Lemma 1 is what makes this the best-scoring candidate of the run, so the returned prompt never scores below the seed; without monotonicity the final leader could fall below a candidate the run had already seen. Gate monotonicity (Proposition 1): the diversity gate is τ t = ϱ ℓ t \tau_t = \varrho\ell_t τ t = ϱ ℓ t , so monotone ℓ t \ell_t ℓ t is what makes τ t \tau_t τ t non-decreasing and a candidate that falls below it permanently ineligible; if ℓ t \ell_t ℓ t could fall the gate reopens and the argument collapses. And the convergence rate (Theorem 4) analyzes the leader score as a monotone accumulator of Δ min \Delta_{\min} Δ m i n increments, which is what makes “improving steps required” a well-defined finite quantity. And the comparison with greedy (Proposition 5) uses it after the displacement step. One result we do not claim as a dependency: Theorem 6 evaluates its gate at a single step and never compares ℓ t \ell_t ℓ t to ℓ t − 1 \ell_{t-1} ℓ t − 1 , so it holds verbatim under re-evaluation.
The contrast with children-only beam search is still sharp: under S b e a m S^{\mathrm{beam}} S beam (Section C.1) the previous leader is never retained, so a step in which all W k Wk W k children score below ℓ t − 1 \ell_{t-1} ℓ t − 1 forces ℓ t < ℓ t − 1 \ell_t < \ell_{t-1} ℓ t < ℓ t − 1 . But Lemma 1 buys this on the score estimate , and the substantive monotonicity statement, the one that constrains behavior rather than fixing a definition, is the next result, which bounds regression of the beam’s best true score under noise.
Theorem 2 is stated in the main text (p. 7).
Corollary 1 is stated in the main text (p. 7).
For W = 4 W = 4 W = 4 , k = 3 k = 3 k = 3 , δ = 0.05 \delta= 0.05 δ = 0.05 and independent batches (c σ = 1 c_\sigma= 1 c σ = 1 at σ 2 = 1 / 4 \sigma^2 = 1/4 σ 2 = 1/4 ), Corollary 1 reads n r e ≥ ε − 2 ln ( 320 ) ≈ 5.77 ε − 2 n_{\mathrm{re}} \ge\varepsilon^{-2}\ln(320) \approx5.77\varepsilon^{-2} n re ≥ ε − 2 ln ( 320 ) ≈ 5.77 ε − 2 : n r e ≥ 145 n_{\mathrm{re}} \ge145 n re ≥ 145 at ε = 0.2 \varepsilon= 0.2 ε = 0.2 , and n r e ≥ 5.8 × 10 4 n_{\mathrm{re}} \ge5.8 \times10^4 n re ≥ 5.8 × 1 0 4 at ε = 0.01 \varepsilon= 0.01 ε = 0.01 . A shared batch doubles both. Read against our per-step training batches (∣ B t ∣ ∈ { 10 , 64 , 216 } |B_t| \in\{10, 64, 216\} ∣ B t ∣ ∈ { 10 , 64 , 216 } ), only BBH’s reaches the ε = 0.2 \varepsilon= 0.2 ε = 0.2 requirement, and a batch of 64 buys ε ≈ 0.30 \varepsilon\approx0.30 ε ≈ 0.30 . So a per-step no-regression guarantee for the re-evaluation regime is coarse at every batch size we use, which is the quantitative reason SPLICE does not select on re-evaluated scores. We have not swept the batch size, so the corollary is a statement about the alternative design rather than one we test.
The two scoring conventions are a trade-off. It would be convenient to read Lemma 1 as the guarantee and Theorem 2 as a fallback for an ablation, but the two are not guaranteed versus realistic but two designs with opposite failure modes. Cached scoring gives deterministic non-regression on the score estimate , but the estimate can be stale: a candidate that drew a lucky batch keeps its inflated score for the rest of the run, so the leader may be a noise artifact. The guarantee is exact; the quantity guaranteed is imperfect. Re-evaluation tracks the true objective more closely, but re-rolls selection-on-noise at every step, so the leader can regress in truth, and Theorem 2 is what bounds that regression, with Corollary 1 naming the batch size that makes it small. Read together: exact monotonicity on a possibly-stale estimate, or probabilistic monotonicity on the true score at a stated batch-size.
The distinction matters when reading the experiments. SPLICE re-runs its beam on a fresh training batch every step to produce critiques, so a log of those scores can move down from one step to the next without contradicting Lemma 1: the lemma is about the cached selection score, not about fresh-batch re-evaluations. Score-progression traces should therefore be read as monotone in the cached score only, not as evidence of a monotone true-objective curve.
The rate counts progress in steps of a fixed size Δ min > 0 \Delta_{\min} > 0 Δ m i n > 0 .
Definition 17 (Δ min \Delta_{\min} Δ m i n -improving proposal). A proposal u ∼ q ϕ ( ⋅ ∣ x , H t ) u \sim q_{\phi}(\cdot\mid x,H_t) u ∼ q ϕ ( ⋅ ∣ x , H t ) is Δ min \Delta_{\min} Δ m i n -improving from x x x iff F ~ ( Apply ( x , u ) ) ≥ F ~ ( x ) + Δ min \widetilde{F}(\operatorname{Apply}(x,u)) \ge\widetilde{F}(x) + \Delta_{\min} F ( Apply ( x , u )) ≥ F ( x ) + Δ m i n .
Selection keeps any improvement, so smaller gains occur and are retained; they never lower the leader, and the definition only decides which proposals the rate counts. With a 0/1 metric and λ = 0 \lambda= 0 λ = 0 , every positive gain on a validation split of n n n examples is at least 1 / n 1/n 1/ n , so Δ min = 1 / n \Delta_{\min} = 1/n Δ m i n = 1/ n makes every improving proposal Δ min \Delta_{\min} Δ m i n -improving. Setting Δ min \Delta_{\min} Δ m i n to SPLICE’s parameter (default 0.005) matches the threshold the algorithm uses for early stopping, but the analysis does not require that choice.
Before stating the rate we fix the quantity it is stated in, since the argument accumulates progress in the scored objective and the conclusion a reader wants is about the population one. Every ingredient of the proof lives in the scored objective F ~ \widetilde{F} F of § 2 : Definition 17 measures improvement in F ~ \widetilde{F} F , and Lemma 1 makes ℓ t = max c t F ~ \ell_t = \max_{c_t} \widetilde{F} ℓ t = max c t F non-decreasing. We therefore state the rate on F ~ \widetilde{F} F and pay the transfer to F ⋆ F^\star F ⋆ explicitly in Corollary 2, rather than assert a population conclusion the accumulation does not deliver. Write x ~ ⋆ ∈ arg max x ∈ X F ~ ( x ) \widetilde{x}^{\star} \in\arg\max_{x \in\mathcal{X}} \widetilde{F}(x) x ⋆ ∈ arg max x ∈ X F ( x ) .
Assumption 5 (Scored coverage). Fix a tolerance ε ≥ Δ min \varepsilon\ge\Delta_{\min} ε ≥ Δ m i n , and let
p ~ ⋆ ( ε ) : = inf H t min x : F ~ ( x ~ ⋆ ) − F ~ ( x ) ≥ ε Pr u ∼ q φ ( ⋅ ∣ x , H t ) [ u is Δ min -improving from x ] . (18) \widetilde{p}^{\star}(\varepsilon) := \inf_{H_t}\ \min_{x:\,\widetilde{F}(\widetilde{x}^{\star})-\widetilde{F}(x)\ge\varepsilon}\Pr_{u\sim q_{\varphi}(\cdot\mid x,H_t)}\left[u\text{ is }\Delta_{\min}\text{-improving from }x\right]. \tag*{(18)} p ⋆ ( ε ) := H t inf x : F ( x ⋆ ) − F ( x ) ≥ ε min u ∼ q φ ( ⋅ ∣ x , H t ) Pr [ u is Δ m i n -improving from x ] . (18) the minimum over states whose score is still ε \varepsilon ε below the best, taken uniformly over histories H t H_t H t , for the realized validation split. We assume p ~ ⋆ ( ε ) > 0 \widetilde{p}^{\star}(\varepsilon)>0 p ⋆ ( ε ) > 0 at this one ε \varepsilon ε .
This is Assumption 1’s minimum-competence condition read on the sublevel set of the objective the algorithm can see, with an improvement counted only when it reaches Δ min \Delta_{\min} Δ m i n . The two conditions range over different sets of states, since validation noise moves states into and out of the sublevel set, and neither implies the other. Theorem 3 needs the population form, because it reasons about the population suboptimality of parents; the rate below needs this one, because the leader is chosen by score.
Theorem 4 is stated in the main text (p. 7).
Corollary 2 (Population form, with the transfer priced). In the setting of Theorem 4, under Assumptions 2 and 3 and with a validation split of n = ∣ D v a l i d ∣ n=|\mathcal{D}_{\mathrm{valid}}| n = ∣ D valid ∣ i.i.d. examples, let ε n \varepsilon_n ε n satisfy 2 ( ∣ B T ∣ + 1 ) exp ( − 2 n ε n 2 ) ≤ δ / 2 2(|B_T|+1)\exp(-2n\varepsilon_n^2)\le\delta/2 2 ( ∣ B T ∣ + 1 ) exp ( − 2 n ε n 2 ) ≤ δ /2 , with B T B_T B T the data-independent ball of Theorem 7 . The quantities p ~ ⋆ \widetilde{p}^{\star} p ⋆ , K K K and p a d v p^{\mathrm{adv}} p adv depend on the realized validation split, and so does the horizon T r e q : = ( 2 K + 8 ln ( 2 / δ ) ) / p a d v ( ε ) T_{\mathrm{req}}:=(2K+8\ln(2/\delta))/p^{\mathrm{adv}}(\varepsilon) T req := ( 2 K + 8 ln ( 2/ δ )) / p adv ( ε ) . Then with probability at least 1 − δ 1-\delta 1 − δ , either Assumption 5 fails at ε \varepsilon ε , or T < T r e q T<T_{\mathrm{req}} T < T req , or
F ⋆ ( leader ( C T ) ) ≥ F ⋆ ( x ⋆ ) − ε − 2 ε n − ∑ j λ j R j ( x ⋆ ) . (19) F^{\star}(\operatorname{leader}(\mathcal{C}_T)) \ge F^{\star}(x^{\star})-\varepsilon-2\varepsilon_n-\sum_j\lambda_jR_j(x^{\star}). \tag*{(19)} F ⋆ ( leader ( C T )) ≥ F ⋆ ( x ⋆ ) − ε − 2 ε n − j ∑ λ j R j ( x ⋆ ) . (19)
Three of the four terms on the right of (19) are the price of reporting a population guarantee for a procedure that optimizes a regularized finite-sample score, and each is separately controllable: ε \varepsilon ε by the horizon, ε n \varepsilon_n ε n by the validation size, ∑ j λ j R j ( x ⋆ ) \sum_j\lambda_jR_j(x^{\star}) ∑ j λ j R j ( x ⋆ ) by the regularization weights (for a single penalty, the term λ κ ( x ⋆ ) \lambda\kappa(x^{\star}) λκ ( x ⋆ ) that Theorem 5 isolates). The first two pull against each other: a longer horizon drives the ε \varepsilon ε requirement down but enlarges B T B_T B T , and ε n \varepsilon_n ε n grows as T log ( Δ G + 1 ) / n \sqrt{T\log(\Delta_{\mathcal{G}}+1)/n} T log ( Δ G + 1 ) / n , so at a fixed validation size the population guarantee does not improve indefinitely with search. What no choice of T T T removes is the gap between x ⋆ x^{\star} x ⋆ and x a l l ⋆ x^{\star}_{\mathrm{all}} x all ⋆ , which is why (11) fixes the target at the best feasible prompt and Proposition 2 prices the rest.
One scope note. SPLICE stops early once the leader has gained less than Δ min \Delta_{\min} Δ m i n (min_improvement) over the last T p a t T_{\mathrm{pat}} T pat steps (five or ten in our runs), so a run can terminate before the horizon Theorem 4 asks for. The bound therefore describes the unstopped process; early stopping trades the guarantee for budget exactly when p a d v p^{\mathrm{adv}} p adv is small enough to make the horizon impractical, and Lemma 1 is what makes that trade safe: the run exits with its monotone best-so-far rather than with a regression.
Two features of Theorem 4 matter. The exponent is k k k , not W k Wk W k : Theorem 3 guarantees a child that beats its own parent, whereas advancing the leader needs a child that beats the leader, and only the leader’s own k k k draws are guaranteed to do that. The rate is therefore conservative, since a child of another lineage can also overtake the incumbent. And the dependence on δ \delta δ is additive with explicit constants rather than an unspecified multiplicative C log ( 1 / δ ) C\log(1/\delta) C log ( 1/ δ ) , which is both sharper and checkable.
The bound has three empirical handles: the numerator scales with the initial gap, the denominator grows with k k k alone, and Δ min \Delta_{\min} Δ m i n enters linearly. The k k k -dependence is the one the rate predicts. Because coverage enters through p ~ ⋆ ( ε ) \widetilde{p}^{\star}(\varepsilon) p ⋆ ( ε ) , the ε \varepsilon ε -dependence is explicit on both sides: tightening the target (smaller ε \varepsilon ε ) enlarges the numerator’s ( h ~ 0 − ε ) (\widetilde{h}_0-\varepsilon) ( h 0 − ε ) term and, because it enlarges the sublevel set over which p ~ ⋆ ( ε ) \widetilde{p}^{\star}(\varepsilon) p ⋆ ( ε ) is a minimum, can only lower p a d v ( ε ) p^{\mathrm{adv}}(\varepsilon) p adv ( ε ) , so T T T grows on both counts. For small p ~ ⋆ \widetilde{p}^{\star} p ⋆ , p a d v ≈ k p ~ ⋆ p^{\mathrm{adv}}\approx k\widetilde{p}^{\star} p adv ≈ k p ⋆ , giving T ∝ 1 / ( k p ~ ⋆ ) T\propto1/(k\widetilde{p}^{\star}) T ∝ 1/ ( k p ⋆ ) , linear in 1 / p ~ ⋆ 1/\widetilde{p}^{\star} 1/ p ⋆ with per-parent fan-out, not beam width, as the practitioner’s compensating lever. When p a d v p^{\mathrm{adv}} p adv becomes very small the bound stays true and reports that the remaining gap is no longer reachable, and early stopping then ends the run with the leader it has.
Proofs
Proof of Lemma 1. Let x t − 1 L ∈ arg max x ∈ C t − 1 F ~ ( x ; D v a l i d ) x_{t-1}^{\mathrm{L}} \in\arg\max_{x\in C_{t-1}} \widetilde{F}(x;D_{\mathrm{valid}}) x t − 1 L ∈ arg max x ∈ C t − 1 F ( x ; D valid ) , so F ~ ( x t − 1 L ) = ℓ t − 1 \widetilde{F}(x_{t-1}^{\mathrm{L}})=\ell_{t-1} F ( x t − 1 L ) = ℓ t − 1 . Three facts combine.
(i) Retention in the frontier. By (6) the frontier is F t = C t − 1 ∪ N t ⊇ C t − 1 F_t=C_{t-1}\cup N_t\supseteq C_{t-1} F t = C t − 1 ∪ N t ⊇ C t − 1 , so x t − 1 L ∈ F t x_{t-1}^{\mathrm{L}}\in F_t x t − 1 L ∈ F t . This is the step that fails for children-only beam search, where F t = N t F_t=N_t F t = N t .
(ii) Score stability. Under the cached-scoring convention, F ~ ( x t − 1 L ; D v a l i d ) \widetilde{F}(x_{t-1}^{\mathrm{L}};D_{\mathrm{valid}}) F ( x t − 1 L ; D valid ) is the value realized when x t − 1 L x_{t-1}^{\mathrm{L}} x t − 1 L was first evaluated and is not recomputed on retention. Hence its score in round t t t equals ℓ t − 1 \ell_{t-1} ℓ t − 1 exactly.
(iii) Elitist selection. S e l i t − d i v S^{\mathrm{elit-div}} S elit − div fills E t E_t E t with the top W − D W-D W − D elements of F t F_t F t by score. Either x t − 1 L ∈ E t x_{t-1}^{\mathrm{L}}\in E_t x t − 1 L ∈ E t , in which case ℓ t ≥ F ~ ( x t − 1 L ) = ℓ t − 1 \ell_t\geq\widetilde{F}(x_{t-1}^{\mathrm{L}})=\ell_{t-1} ℓ t ≥ F ( x t − 1 L ) = ℓ t − 1 ; or it is excluded, which by the definition of “top W − D W-D W − D by score” requires at least W − D W-D W − D elements of F t F_t F t with score at least F ~ ( x t − 1 L ) \widetilde{F}(x_{t-1}^{\mathrm{L}}) F ( x t − 1 L ) , all of which are in E t ⊆ C t E_t\subseteq C_t E t ⊆ C t , so again ℓ t ≥ ℓ t − 1 \ell_t\geq\ell_{t-1} ℓ t ≥ ℓ t − 1 .
In both cases ℓ t ≥ ℓ t − 1 \ell_t\geq\ell_{t-1} ℓ t ≥ ℓ t − 1 , and t t t was arbitrary.
Proof of Theorem 2. Here every member of F t F_t F t is re-evaluated at step t t t on n r e n_{\mathrm{re}} n re fresh examples and selection acts on F ^ n r e \widehat{F}_{n_{\mathrm{re}}} F n re , so the cached-scoring argument above is unavailable. Write f t ⋆ = max x ∈ C t F ⋆ ( x ) f_t^\star=\max_{x\in C_t}F^\star(x) f t ⋆ = max x ∈ C t F ⋆ ( x ) and let x ˉ t − 1 ∈ arg max x ∈ C t − 1 F ⋆ ( x ) \bar{x}_{t-1}\in\arg\max_{x\in C_{t-1}}F^\star(x) x ˉ t − 1 ∈ arg max x ∈ C t − 1 F ⋆ ( x ) . Condition on everything up to the drawing of the step-t t t evaluation examples. The frontier F t F_t F t is then fixed (its parents were chosen at step t − 1 t-1 t − 1 and its children by the proposer), and x ˉ t − 1 ∈ F t \bar{x}_{t-1}\in F_t x ˉ t − 1 ∈ F t is fixed with it; only the step-t t t estimates remain random.
Suppose the regression event { f t ⋆ < f t − 1 ⋆ − ε } \{f_t^\star<f_{t-1}^\star-\varepsilon\} { f t ⋆ < f t − 1 ⋆ − ε } occurs. Then x ˉ t − 1 \bar{x}_{t-1} x ˉ t − 1 was not retained. The selector is elitist, so the top-scoring member x ′ x^\prime x ′ of F t F_t F t is retained, and since x ˉ t − 1 ∈ F t \bar{x}_{t-1}\in F_t x ˉ t − 1 ∈ F t was not, x ′ ≠ x ˉ t − 1 x^\prime\neq\bar{x}_{t-1} x ′ = x ˉ t − 1 and F ^ n r e ( x ′ ) ≥ F ^ n r e ( x ˉ t − 1 ) \widehat{F}_{n_{\mathrm{re}}}(x^\prime)\geq\widehat{F}_{n_{\mathrm{re}}}(\bar{x}_{t-1}) F n re ( x ′ ) ≥ F n re ( x ˉ t − 1 ) ; and every retained candidate has F ⋆ ( x ′ ) ≤ f t ⋆ < f t − 1 ⋆ − ε F^\star(x^\prime)\leq f_t^\star<f_{t-1}^\star-\varepsilon F ⋆ ( x ′ ) ≤ f t ⋆ < f t − 1 ⋆ − ε . Hence there is x ′ ∈ F t ∖ { x ˉ t − 1 } x^\prime\in F_t\setminus\{\bar{x}_{t-1}\} x ′ ∈ F t ∖ { x ˉ t − 1 } with
F ⋆ ( x ˉ t − 1 ) − F ⋆ ( x ′ ) > ε and F ^ n r e ( x ′ ) ≥ F ^ n r e ( x ˉ t − 1 ) . (20) F^\star(\bar{x}_{t-1})-F^\star(x^\prime)>\varepsilon
\qquad\text{and}\qquad
\widehat{F}_{n_{\mathrm{re}}}(x^\prime)\geq\widehat{F}_{n_{\mathrm{re}}}(\bar{x}_{t-1}). \tag*{(20)} F ⋆ ( x ˉ t − 1 ) − F ⋆ ( x ′ ) > ε and F n re ( x ′ ) ≥ F n re ( x ˉ t − 1 ) . (20)
Writing η ( x ) : = F ^ n r e ( x ) − F ⋆ ( x ) \eta(x):=\widehat{F}_{n_{\mathrm{re}}}(x)-F^\star(x) η ( x ) := F n re ( x ) − F ⋆ ( x ) , this gives η ( x ′ ) − η ( x ˉ t − 1 ) > ε \eta(x^\prime)-\eta(\bar{x}_{t-1})>\varepsilon η ( x ′ ) − η ( x ˉ t − 1 ) > ε for that x ′ x^\prime x ′ .
Fix any x ′ ∈ F t ∖ { x ˉ t − 1 } x^\prime\in F_t\setminus\{\bar{x}_{t-1}\} x ′ ∈ F t ∖ { x ˉ t − 1 } with population gap above ε \varepsilon ε . If the two candidates are scored on independent batches, each η \eta η is mean-zero sub-Gaussian with proxy σ 2 / n r e \sigma^2/n_{\mathrm{re}} σ 2 / n re (Lemma 2), their difference has proxy 2 σ 2 / n r e 2\sigma^2/n_{\mathrm{re}} 2 σ 2 / n re (Lemma 3), and Pr [ η ( x ′ ) − η ( x ˉ t − 1 ) > ε ] ≤ exp ( − n r e ε 2 / 4 σ 2 ) \Pr[\eta(x^\prime)-\eta(\bar{x}_{t-1})>\varepsilon]\leq\exp(-n_{\mathrm{re}}\varepsilon^2/4\sigma^2) Pr [ η ( x ′ ) − η ( x ˉ t − 1 ) > ε ] ≤ exp ( − n re ε 2 /4 σ 2 ) . If they share a batch, the difference is a mean of n r e n_{\mathrm{re}} n re i.i.d. per-example differences in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , and Hoeffding’s inequality gives exp ( − 2 n r e ε 2 / 2 2 ) = exp ( − n r e ε 2 / 2 ) \exp(-2n_{\mathrm{re}}\varepsilon^2/2^2)=\exp(-n_{\mathrm{re}}\varepsilon^2/2) exp ( − 2 n re ε 2 / 2 2 ) = exp ( − n re ε 2 /2 ) . Both are exp ( − n r e ε 2 / c σ ) \exp(-n_{\mathrm{re}}\varepsilon^2/c_\sigma) exp ( − n re ε 2 / c σ ) for the stated c σ c_\sigma c σ .
Because F t F_t F t is fixed given the conditioning, a union bound over its at most ∣ F t ∣ − 1 |F_t|-1 ∣ F t ∣ − 1 members other than x ˉ t − 1 \bar{x}_{t-1} x ˉ t − 1 is valid and gives Theorem 2. Taking the union over the retained beam C t C_t C t instead, as a smaller prefactor would suggest, would not be correct: C t C_t C t is chosen by the very event being bounded (Remark 12). Finally ∣ F t ∣ ≤ ∣ C t − 1 ∣ + k ∣ C t − 1 ∣ ≤ W ( 1 + k ) |F_t|\leq|C_{t-1}|+k|C_{t-1}|\leq W(1+k) ∣ F t ∣ ≤ ∣ C t − 1 ∣ + k ∣ C t − 1 ∣ ≤ W ( 1 + k ) , and integrating over the conditioning preserves the bound.
Proof of Corollary 1. Impose W ( 1 + k ) exp ( − n r e ε 2 / c σ ) ≤ δ W(1+k)\exp(-n_{\mathrm{re}}\varepsilon^2/c_\sigma)\leq\delta W ( 1 + k ) exp ( − n re ε 2 / c σ ) ≤ δ , which implies the conclusion of the corollary through Theorem 2, since ∣ F t ∣ − 1 < W ( 1 + k ) |F_t|-1<W(1+k) ∣ F t ∣ − 1 < W ( 1 + k ) . Taking logarithms gives n r e ≥ ( c σ / ε 2 ) ln ( W ( 1 + k ) / δ ) n_{\mathrm{re}}\geq(c_\sigma/\varepsilon^2)\ln(W(1+k)/\delta) n re ≥ ( c σ / ε 2 ) ln ( W ( 1 + k ) / δ ) , which is Corollary 1. With W = 4 W=4 W = 4 , k = 3 k=3 k = 3 , δ = 0.05 \delta=0.05 δ = 0.05 , c σ = 1 c_\sigma=1 c σ = 1 : n r e ≥ ε − 2 ln 320 n_{\mathrm{re}}\geq\varepsilon^{-2}\ln320 n re ≥ ε − 2 ln 320 , i.e. 145 145 145 at ε = 0.2 \varepsilon=0.2 ε = 0.2 and 5.77 × 10 4 5.77\times10^4 5.77 × 1 0 4 at ε = 0.01 \varepsilon=0.01 ε = 0.01 .
Proof of Theorem 4. Let h ~ 0 = F ~ ( x ~ ⋆ ) − F ~ ( x ( 0 ) ) \widetilde{h}_0=\widetilde{F}(\widetilde{x}^\star)-\widetilde{F}(x^{(0)}) h 0 = F ( x ⋆ ) − F ( x ( 0 ) ) and K : = ⌈ ( h ~ 0 − ε ) / Δ min ⌉ K:=\left\lceil(\widetilde{h}_0-\varepsilon)/\Delta_{\min}\right\rceil K := ⌈ ( h 0 − ε ) / Δ m i n ⌉ . Every quantity in this proof is the scored objective F ~ \widetilde{F} F ; the transfer to F ⋆ F^\star F ⋆ is Corollary 2. If K ≤ 0 K\leq0 K ≤ 0 then h ~ 0 ≤ ε \widetilde{h}_0\leq\varepsilon h 0 ≤ ε , so the target already holds at t = 0 t=0 t = 0 and, by Lemma 1, at every T T T ; we assume K ≥ 1 K\geq1 K ≥ 1 below, as Lemma 4 requires.
Step 1: a bounded number of advances suffices. Call step t t t an advance if ℓ t ≥ ℓ t − 1 + Δ min \ell_t \ge\ell_{t-1}+\Delta_{\min} ℓ t ≥ ℓ t − 1 + Δ m i n . By Lemma 1 the leader score is non-decreasing, so it never gives back progress and the advances accumulate. Each advance raises the leader by at least Δ min \Delta_{\min} Δ m i n , so after K K K advances the leader has gained at least K Δ min ≥ h ~ 0 − ε K\Delta_{\min}\ge\tilde{h}_0-\varepsilon K Δ m i n ≥ h ~ 0 − ε , leaving F ~ ( x ~ ⋆ ) − ℓ t ≤ ε \tilde{F}(\tilde{x}^{\star})-\ell_t\le\varepsilon F ~ ( x ~ ⋆ ) − ℓ t ≤ ε ; that is, K K K advances suffice for ε \varepsilon ε -optimality in F ~ \tilde{F} F ~ . Note that K K K is a ratio of two quantities in the same units, which is what makes it the right count; dividing a population gap by a scored increment would not be.
Step 2: each step advances with probability at least p a d v p^{\mathrm{adv}} p adv . Let t ε : = min { t : F ~ ( x ~ ⋆ ) − ℓ t ≤ ε } t_\varepsilon:=\min\{t:\tilde{F}(\tilde{x}^{\star})-\ell_t\le\varepsilon\} t ε := min { t : F ~ ( x ~ ⋆ ) − ℓ t ≤ ε } be the first ε \varepsilon ε -optimal step, and fix t ≤ t ε t\le t_\varepsilon t ≤ t ε . Let x t − 1 L x^L_{t-1} x t − 1 L denote the current leader; since t ≤ t ε t\le t_\varepsilon t ≤ t ε it satisfies F ~ ( x ~ ⋆ ) − F ~ ( x t − 1 L ) ≥ ε \tilde{F}(\tilde{x}^{\star})-\tilde{F}(x^L_{t-1})\ge\varepsilon F ~ ( x ~ ⋆ ) − F ~ ( x t − 1 L ) ≥ ε , so it lies in the sublevel set of (18) . The leader contributes k k k of the expansion’s draws. Each is Δ min \Delta_{\min} Δ m i n -improving from x t − 1 L x^L_{t-1} x t − 1 L (Definition 17) with probability at least p ~ ⋆ ( ε ) \tilde{p}^{\star}(\varepsilon) p ~ ⋆ ( ε ) by (18) , and by (6) they are i.i.d. given the history, so
Pr [ some child of the leader beats it by at least Δ min ] ≥ 1 − ( 1 − p ~ ⋆ ( ε ) ) k = : p a d v ( ε ) . \Pr\left[\text{some child of the leader beats it by at least }\Delta_{\min}\right]\ge1-\left(1-\tilde{p}^{\star}(\varepsilon)\right)^k=:p^{\mathrm{adv}}(\varepsilon). Pr [ some child of the leader beats it by at least Δ m i n ] ≥ 1 − ( 1 − p ~ ⋆ ( ε ) ) k =: p adv ( ε ) .
Any such child lies in F t \mathcal{F}_t F t and scores at least ℓ t − 1 + Δ min \ell_{t-1}+\Delta_{\min} ℓ t − 1 + Δ m i n , so by the elitist argument of Lemma 1 the new leader satisfies ℓ t ≥ ℓ t − 1 + Δ min \ell_t\ge\ell_{t-1}+\Delta_{\min} ℓ t ≥ ℓ t − 1 + Δ m i n : the step is an advance. The bound holds conditionally on the entire past, since p ~ ⋆ ( ε ) \tilde{p}^{\star}(\varepsilon) p ~ ⋆ ( ε ) is a uniform lower bound over states in the sublevel set and over histories.
Step 3: Chernoff, with the indicators patched after the target is met. Let I t I_t I t indicate that step t t t is an advance. Step 2 bounds its conditional success probability only for t ≤ t ε t\le t_\varepsilon t ≤ t ε , so set I t ′ : = I t 1 { t ≤ t ε } + 1 { t > t ε } I'_t:=I_t\mathbf{1}\{t\le t_\varepsilon\}+\mathbf{1}\{t>t_\varepsilon\} I t ′ := I t 1 { t ≤ t ε } + 1 { t > t ε } . The event { t ≤ t ε } \{t\le t_\varepsilon\} { t ≤ t ε } is fixed by the past at step t t t , since it says the target was not met by step t − 1 t-1 t − 1 , so every I t ′ I'_t I t ′ has conditional success probability at least p a d v ( ε ) p^{\mathrm{adv}}(\varepsilon) p adv ( ε ) given the past, and Lemma 4 with p = p a d v ( ε ) p=p^{\mathrm{adv}}(\varepsilon) p = p adv ( ε ) applies to N T ′ : = ∑ t ≤ T I t ′ N'_T:=\sum_{t\le T}I'_t N T ′ := ∑ t ≤ T I t ′ :
T ≥ 2 K + 8 ln ( 1 / δ ) p a d v ( ε ) ⟹ Pr [ N T ′ < K ] ≤ δ . T\ge\frac{2K+8\ln(1/\delta)}{p^{\mathrm{adv}}(\varepsilon)}
\quad\Longrightarrow\quad
\Pr[N'_T<K]\le\delta. T ≥ p adv ( ε ) 2 K + 8 ln ( 1/ δ ) ⟹ Pr [ N T ′ < K ] ≤ δ .
On { t ε > T } \{t_\varepsilon>T\} { t ε > T } every I t ′ I'_t I t ′ equals I t I_t I t , so N T ′ N'_T N T ′ is the number of advances, which is below K K K by Step 1. Hence Pr [ t ε > T ] ≤ Pr [ N T ′ < K ] ≤ δ \Pr[t_\varepsilon>T]\le\Pr[N'_T<K]\le\delta Pr [ t ε > T ] ≤ Pr [ N T ′ < K ] ≤ δ . On { t ε ≤ T } \{t_\varepsilon\le T\} { t ε ≤ T } the target is met at t ε t_\varepsilon t ε and kept to T T T by Lemma 1, since ℓ T ≥ ℓ t ε \ell_T\ge\ell_{t_\varepsilon} ℓ T ≥ ℓ t ε . So F ~ ( leader ( C T ) ) ≥ F ~ ( x ~ ⋆ ) − ε \tilde{F}(\operatorname{leader}(C_T))\ge\tilde{F}(\tilde{x}^{\star})-\varepsilon F ~ ( leader ( C T )) ≥ F ~ ( x ~ ⋆ ) − ε with probability at least 1 − δ 1-\delta 1 − δ , which is Theorem 4. □
Proof of Corollary 2. Write x ^ : = leader ( C T ) \hat{x}:=\operatorname{leader}(C_T) x ^ := leader ( C T ) and n : = ∣ D v a l i d ∣ n:=|\mathcal{D}_{\mathrm{valid}}| n := ∣ D valid ∣ . Apply Theorem 7 (i) to the set U : = B T ∪ { x ⋆ } \mathcal{U}:=\mathcal{B}_T\cup\{x^{\star}\} U := B T ∪ { x ⋆ } . It is fixed independently of D v a l i d \mathcal{D}_{\mathrm{valid}} D valid : B T \mathcal{B}_T B T is determined by the edit graph and the seed, and x ⋆ x^{\star} x ⋆ by F ⋆ F^{\star} F ⋆ and X \mathcal{X} X . In the setting of Theorem 4 scores are cached per state, so each member of U \mathcal{U} U carries one score and the factor T + 1 T+1 T + 1 of Theorem 7 (ii) does not arise. The set contains x ^ \hat{x} x ^ , since x ^ ∈ H T ⊆ B T \hat{x}\in\mathcal{H}_T\subseteq\mathcal{B}_T x ^ ∈ H T ⊆ B T by Theorem 7 (ii). Using the history itself as the union set would not be valid, for the reason Remark 12 gives. By hypothesis 2 ( ∣ B T ∣ + 1 ) exp ( − 2 n ε n 2 ) ≤ δ / 2 2(|\mathcal{B}_T|+1)\exp(-2n\varepsilon_n^2)\le\delta/2 2 ( ∣ B T ∣ + 1 ) exp ( − 2 n ε n 2 ) ≤ δ /2 , so with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
∣ F ^ n ( x ) − F ⋆ ( x ) ∣ ≤ ε n for every x ∈ B T ∪ { x ⋆ } . (21) \left|\widehat{F}_n(x)-F^{\star}(x)\right|\le\varepsilon_n
\qquad\text{for every }x\in\mathcal{B}_T\cup\{x^{\star}\}. \tag*{(21)} F n ( x ) − F ⋆ ( x ) ≤ ε n for every x ∈ B T ∪ { x ⋆ } . (21)
Conditional on the validation split and the scores, Theorem 4 at confidence δ / 2 \delta/2 δ /2 , which is what the 8 ln ( 2 / δ ) 8\ln(2/\delta) 8 ln ( 2/ δ ) term provides, applies whenever Assumption 5 holds and T ≥ T r e q T\ge T_{\mathrm{req}} T ≥ T req . So the event that both hold and the conclusion of Theorem 4 fails has probability at most δ / 2 \delta/2 δ /2 , with the failure of (21) the total is at most δ \delta δ . The hypothesis and T r e q T_{\mathrm{req}} T req depend on the split, which is why the corollary is stated as this joint bound rather than conditionally on the hypothesis. Outside the two failure events, either the hypothesis fails, or T < T r e q T<T_{\mathrm{req}} T < T req , or three inequalities compose. First, since every R j ≥ 0 R_j\ge0 R j ≥ 0 and x ^ ∈ B T \hat{x}\in\mathcal{B}_T x ^ ∈ B T ,
F ⋆ ( x ^ ) ≥ F ^ n ( x ^ ) − ε n = F ~ ( x ^ ) + ∑ j λ j R j ( x ^ ) − ε n ≥ F ~ ( x ^ ) − ε n . F^{\star}(\hat{x})\ge\widehat{F}_n(\hat{x})-\varepsilon_n=\tilde{F}(\hat{x})+\sum_j\lambda_jR_j(\hat{x})-\varepsilon_n\ge\tilde{F}(\hat{x})-\varepsilon_n. F ⋆ ( x ^ ) ≥ F n ( x ^ ) − ε n = F ~ ( x ^ ) + j ∑ λ j R j ( x ^ ) − ε n ≥ F ~ ( x ^ ) − ε n .
Second, Theorem 4 gives F ~ ( x ^ ) ≥ F ~ ( x ~ ⋆ ) − ε \tilde{F}(\hat{x})\ge\tilde{F}(\tilde{x}^{\star})-\varepsilon F ~ ( x ^ ) ≥ F ~ ( x ~ ⋆ ) − ε , and x ~ ⋆ \tilde{x}^{\star} x ~ ⋆ maximizes F ~ \tilde{F} F ~ over X ⊇ x ⋆ \mathcal{X}\supseteq x^{\star} X ⊇ x ⋆ , so F ~ ( x ^ ) ≥ F ~ ( x ⋆ ) − ε \tilde{F}(\hat{x})\ge\tilde{F}(x^{\star})-\varepsilon F ~ ( x ^ ) ≥ F ~ ( x ⋆ ) − ε . Third,
F ~ ( x ⋆ ) = F ^ n ( x ⋆ ) − ∑ j λ j R j ( x ⋆ ) ≥ F ⋆ ( x ⋆ ) − ε n − ∑ j λ j R j ( x ⋆ ) \tilde{F}(x^{\star})=\widehat{F}_n(x^{\star})-\sum_j\lambda_jR_j(x^{\star})\ge F^{\star}(x^{\star})-\varepsilon_n-\sum_j\lambda_jR_j(x^{\star}) F ~ ( x ⋆ ) = F n ( x ⋆ ) − j ∑ λ j R j ( x ⋆ ) ≥ F ⋆ ( x ⋆ ) − ε n − j ∑ λ j R j ( x ⋆ )
by (21) . Chaining the three gives (19) . □
driven down by a choice the practitioner controls. The quantity that no horizon reduces is the one (20) does not contain: the gap between x ⋆ x^\star x ⋆ and x a l l ⋆ x^\star_{\mathrm{all}} x all ⋆ . Stating the corollary against x ⋆ x^\star x ⋆ rather than x a l l ⋆ x^\star_{\mathrm{all}} x all ⋆ is therefore not a weakening for convenience: against x a l l ⋆ x^\star_{\mathrm{all}} x all ⋆ the conclusion would be unreachable at every T T T whenever freezing costs more than ε \varepsilon ε , and (19)'s sublevel set would contain states with no improving neighbor, making the hypothesis false as well. Proposition 2 is where that gap is addressed, and it is addressed as a price rather than as a rate.
Remark 10 (Why the rate carries k k k and not W k Wk W k ). Step 2 uses only the k k k draws taken from the leader, because those are the ones whose improvement is guaranteed to move ℓ t \ell_t ℓ t : a child improving on a non-leader parent need not exceed ℓ t − 1 \ell_{t-1} ℓ t − 1 (Remark 2). The resulting rate p a d v = 1 − ( 1 − p ~ ⋆ ) k p^{\mathrm{adv}} = 1 - (1-\tilde p^\star)^k p adv = 1 − ( 1 − p ~ ⋆ ) k is therefore conservative: children of other lineages can also exceed the incumbent leader, and nothing in the bound credits them. It should not be replaced by the reachability rate p s t e p = 1 − ( 1 − p ⋆ ) ∣ C t − 1 ∣ k p^{\mathrm{step}} = 1-(1-p^\star)^{|C_{t-1}|k} p step = 1 − ( 1 − p ⋆ ) ∣ C t − 1 ∣ k of Theorem 3, which bounds a different event (some child beats its own parent) under a different coverage condition; using it would overstate what reachability supports, so we keep both quantities and label which is which, in the theory and in Section F.4.1.
Diversity Preservation and the Quality Gate
Monotonicity describes the leader score but says nothing about the beam's lineage structure . Under pure elitism (D = 0 D=0 D = 0 ) the leader climbs while all beam members may become descendants of one early winner (beam collapse).
Definition 18 (Beam collapse). Let anc ( x ) : = lineage ( x ) ∖ { id ( x ) } \operatorname{anc}(x) := \operatorname{lineage}(x)\setminus\{\operatorname{id}(x)\} anc ( x ) := lineage ( x ) ∖ { id ( x )} denote the proper ancestors of x x x , and anc ∘ ( x ) : = anc ( x ) ∖ { id ( x ( 0 ) ) } \operatorname{anc}^{\circ}(x) := \operatorname{anc}(x) \setminus\{\operatorname{id}(x^{(0)})\} anc ∘ ( x ) := anc ( x ) ∖ { id ( x ( 0 ) )} those other than the seed. A beam C C C with at least two members is collapsed if every pair of distinct members shares an ancestor other than the seed, that is, if no x ≠ x ′ x \ne x' x = x ′ in C C C have anc ∘ ( x ) ∩ anc ∘ ( x ′ ) = ∅ \operatorname{anc}^{\circ}(x) \cap\operatorname{anc}^{\circ}(x') = \varnothing anc ∘ ( x ) ∩ anc ∘ ( x ′ ) = ∅ .
The seed has to be excluded, because every candidate after the first step descends from it. That is also the subtlety in Algorithm 3: its Tier 1 and Tier 2 tests check disjointness of anc \operatorname{anc} anc , which includes the seed, so a candidate other than the seed can pass them only while the seed is the sole elite. The selector we ran therefore enforces diversity through its third tier (a distinct immediate parent) and through the backfill of Algorithm 2, and the guarantee below is stated for that mechanism. A selector that applied the same tests to anc ∘ \operatorname{anc}^{\circ} anc ∘ would enforce the stronger, lineage-level property; we state what it would guarantee but did not run it.
Theorem 6 (Diversity preservation). Part (i) is Theorem 1. Let 1 ≤ D ≤ W − 1 1 \le D \le W-1 1 ≤ D ≤ W − 1 , ϱ ∈ [ 0 , 1 ] \varrho\in[0,1] ϱ ∈ [ 0 , 1 ] , and let E t E_t E t be the elite slots of Algorithm 2.
(i) (As run.) If F t F_t F t contains c ⋆ c^\star c ⋆ with F ~ ( c ⋆ ) ≥ ϱ ⋅ ℓ t \tilde F(c^\star) \ge\varrho\cdot\ell_t F ~ ( c ⋆ ) ≥ ϱ ⋅ ℓ t whose parent is not the parent of any elite, then C t C_t C t contains a member scoring at least ϱ ⋅ ℓ t \varrho\cdot\ell_t ϱ ⋅ ℓ t whose parent is not the parent of any elite.
(ii) (Lineage-level variant.) If the Tier 1–2 tests of Algorithm 3 use anc ∘ \operatorname{anc}^{\circ} anc ∘ in place of anc \operatorname{anc} anc , and F t F_t F t contains c ⋆ c^\star c ⋆ with F ~ ( c ⋆ ) ≥ ϱ ⋅ ℓ t \tilde F(c^\star) \ge\varrho\cdot\ell_t F ~ ( c ⋆ ) ≥ ϱ ⋅ ℓ t and anc ∘ ( c ⋆ ) ∩ anc ∘ ( e ) = ∅ \operatorname{anc}^{\circ}(c^\star) \cap\operatorname{anc}^{\circ}(e) = \varnothing anc ∘ ( c ⋆ ) ∩ anc ∘ ( e ) = ∅ for every elite e e e , then C t C_t C t is not collapsed whenever it has at least two members.
The guarantee is conditional : the selector retains a distinct-parent (or, in the variant, lineage-disjoint) competitive candidate when one exists; generating one is the proposer's job. Part (i) is also weak by design. Two members with different parents may still share a recent ancestor, so it rules out the beam narrowing to one parent's children, not to one lineage. That is the property the D D D -sweep of § 4 exercises, and its effect there is large; whether the lineage-level variant would add to it is untested.
Proposition 1 is stated in the main text (p. 6).
Proposition 1 is what an annealing reading of the gate rests on, and it is all that is proved: the gate rises with the leader, so a candidate that falls below it is never readmitted. The reading itself is that early on ℓ t \ell_t ℓ t is low and many candidates qualify for the diversity slots, while late the gate admits only competitive ones, a shift from exploration to exploitation with no temperature parameter. That shift is not a theorem, because eligibility compares a candidate with the leader, F ~ ( c ) ≥ ϱ ℓ t \widetilde{F}(c) \ge\varrho\ell_t F ( c ) ≥ ϱ ℓ t , and whether fewer candidates qualify later depends on how new children score relative to a rising leader, which the selector does not control; children whose scores rise with the leader stay eligible. The exclusion is per candidate, not per lineage: a lineage whose current members fall below the gate can re-enter through a new, higher-scoring child. With ϱ = 0 \varrho= 0 ϱ = 0 the gate is inactive and the proposition is empty; Section F.1 records which runs set ϱ > 0 \varrho> 0 ϱ > 0 . We do not report a lineage-count trajectory or a ϱ \varrho ϱ -sweep, so the schedule is neither proved nor measured.
Proofs
Proof of Theorem 6. Write E t \mathcal{E}_t E t for the elites, P = { parent ( e ) : e ∈ E t } P = \{\operatorname{parent}(e) : e \in\mathcal{E}_t\} P = { parent ( e ) : e ∈ E t } for their parents, and Q t = F t ∖ E t Q_t = \mathcal{F}_t \setminus\mathcal{E}_t Q t = F t ∖ E t for the pool PICKDIVERSE (Algorithm 3) scans in descending score order. Since D ≤ W − 1 D \le W - 1 D ≤ W − 1 , E t ≠ ∅ \mathcal{E}_t \ne\varnothing E t = ∅ , and since the elites are the top of the frontier, ℓ t = max e ∈ E t F ~ \ell_t = \max_{e \in\mathcal{E}_t} \widetilde{F} ℓ t = max e ∈ E t F , so the gate is τ t = ϱ ℓ t \tau_t = \varrho\ell_t τ t = ϱ ℓ t . If Algorithm 2 takes its degenerate branch (∣ F t ∣ ≤ W |\mathcal{F}_t| \le W ∣ F t ∣ ≤ W or N t = ∅ N_t = \varnothing N t = ∅ ) it returns the top min ( W , ∣ F t ∣ ) \min(W, |\mathcal{F}_t|) min ( W , ∣ F t ∣ ) of the frontier; in the first case that is all of F t \mathcal{F}_t F t , which contains c ⋆ c^\star c ⋆ and an elite and so the claim holds directly, and we assume the main branch below.
Part (i). c ⋆ ∉ E t c^\star\notin\mathcal{E}_t c ⋆ ∈ / E t , since an elite’s parent lies in P P P by definition. So c ⋆ ∈ Q t c^\star\in Q_t c ⋆ ∈ Q t , and because the scan is in descending score order and F ~ ( c ⋆ ) ≥ τ t \widetilde{F}(c^\star) \ge\tau_t F ( c ⋆ ) ≥ τ t , no break occurs before c ⋆ c^\star c ⋆ is reached. If Tier 1 or Tier 2 returns some c ′ c' c ′ , then anc ( c ′ ) ∩ Λ = ∅ \operatorname{anc}(c') \cap\Lambda= \varnothing anc ( c ′ ) ∩ Λ = ∅ . Every non-seed elite e e e has parent ( e ) ∈ anc ( e ) ⊆ Λ \operatorname{parent}(e) \in\operatorname{anc}(e) \subseteq\Lambda parent ( e ) ∈ anc ( e ) ⊆ Λ . So if c ′ c' c ′ is not the seed, parent ( c ′ ) ∈ anc ( c ′ ) \operatorname{parent}(c') \in\operatorname{anc}(c') parent ( c ′ ) ∈ anc ( c ′ ) differs from the parent of every non-seed elite, and also from the seed’s undefined parent, which lies in P P P only when the seed is an elite (for instance its sole elite). If c ′ c' c ′ is the seed, the seed is not an elite and P P P holds no undefined parent. Either way parent ( c ′ ) ∉ P \operatorname{parent}(c') \notin P parent ( c ′ ) ∈ / P . Otherwise Tier 3 reaches c ⋆ c^\star c ⋆ , which satisfies parent ( c ⋆ ) ∉ P \operatorname{parent}(c^\star) \notin P parent ( c ⋆ ) ∈ / P , so it returns c ⋆ c^\star c ⋆ or an earlier c ′ ′ c'' c ′′ with parent ( c ′ ′ ) ∉ P \operatorname{parent}(c'') \notin P parent ( c ′′ ) ∈ / P . In every case the first diversity pick has a parent outside P P P and, since the scan stops at the gate, a score of at least τ t = ϱ ℓ t \tau_t = \varrho\ell_t τ t = ϱ ℓ t .
Part (ii). If c ⋆ ∈ E t c^\star\in\mathcal{E}_t c ⋆ ∈ E t , the hypothesis applied to e = c ⋆ e = c^\star e = c ⋆ gives anc ∘ ( c ⋆ ) = ∅ \operatorname{anc}^{\circ}(c^\star) = \varnothing anc ∘ ( c ⋆ ) = ∅ , so c ⋆ c^\star c ⋆ has disjoint non-seed ancestry from every other member of C t C_t C t , and the beam is not collapsed as soon as it has a second member, which the statement assumes. (The selector returns a single candidate only when every non-elite candidate falls below the gate and W − D = 1 W - D = 1 W − D = 1 .) Otherwise c ⋆ ∈ Q t c^\star\in Q_t c ⋆ ∈ Q t , it clears the gate, and it passes Tier 2 on anc ∘ \operatorname{anc}^{\circ} anc ∘ , so the scan returns c ⋆ c^\star c ⋆ or an earlier pick passing Tier 1 or Tier 2, either of which has anc ∘ \operatorname{anc}^{\circ} anc ∘ disjoint from every elite’s. That pick and any elite form the required pair, so C t C_t C t is not collapsed in the sense of Definition 18. □
Proof of Proposition 1. By Lemma 1, ℓ t ≥ ℓ t − 1 \ell_t \ge\ell_{t-1} ℓ t ≥ ℓ t − 1 ; since ϱ > 0 \varrho> 0 ϱ > 0 , multiplying through gives τ t = ϱ ℓ t ≥ ϱ ℓ t − 1 = τ t − 1 \tau_t = \varrho\ell_t \ge\varrho\ell_{t-1} = \tau_{t-1} τ t = ϱ ℓ t ≥ ϱ ℓ t − 1 = τ t − 1 , so the gate sequence is non-decreasing.
For the exclusion claim, suppose F ~ ( x ) < τ t \widetilde{F}(x) < \tau_t F ( x ) < τ t for some candidate x x x and step t t t . With scores cached per state F ~ ( x ) \widetilde{F}(x) F ( x ) is a fixed number, unchanged at every later step, while τ s ≥ τ t \tau_s \ge\tau_t τ s ≥ τ t for all s ≥ t s \ge t s ≥ t by the first part. Hence F ~ ( x ) < τ s \widetilde{F}(x) < \tau_s F ( x ) < τ s , and x x x fails the gate of Algorithm 3 at every s ≥ t s \ge t s ≥ t . The claim is about states only: new children of the same lineage are new states with new scores and may clear the gate. Without the per-state cache the claim holds per evaluation: a state re-proposed after leaving the beam is scored afresh and may clear the gate. Caching is essential: under re-evaluation F ~ ( x ) \widetilde{F}(x) F ( x ) is re-drawn each step and a candidate below the gate can re-enter, which is the regime Theorem 2 governs. □
Generalization, Regularization, and the Price of Freezing
Three results close the analysis: a uniform-convergence bound relating empirical and population scores across the search (Theorem 7), the bias of length regularization (Theorem 5), and the approximation penalty of restricting search to mutable blocks (Proposition 2).
Theorem 7 (Uniform convergence over the search history). Let H T : = ⋃ t = 0 T ( C t ∪ N t ) \mathcal{H}_T := \bigcup_{t=0}^{T}(\mathcal{C}_t \cup\mathcal{N}_t) H T := ⋃ t = 0 T ( C t ∪ N t ) be the evaluated history, let B T : = { x ∈ X : d G ( x ( 0 ) , x ) ≤ T } \mathcal{B}_T := \{x \in\mathcal{X} : d_{\mathcal{G}}(x^{(0)}, x) \le T\} B T := { x ∈ X : d G ( x ( 0 ) , x ) ≤ T } be the radius-T T T ball of the edit graph around the seed, and let Δ G \Delta_{\mathcal{G}} Δ G be the maximum degree of G \mathcal{G} G , so that ∣ B T ∣ ≤ min { ∣ X ∣ , ( Δ G + 1 ) T } |\mathcal{B}_T| \le\min\{|\mathcal{X}|,(\Delta_{\mathcal{G}}+1)^T\} ∣ B T ∣ ≤ min { ∣ X ∣ , ( Δ G + 1 ) T } . Under Assumption 3 and a validation split D v a l i d \mathcal{D}_{\mathrm{valid}} D valid of n n n i.i.d. examples:
(i) for any set U ⊆ X \mathcal{U} \subseteq\mathcal{X} U ⊆ X fixed independently of D v a l i d \mathcal{D}_{\mathrm{valid}} D valid ,
Pr [ sup x ∈ U ∣ F ^ n ( x ) − F ∗ ( x ) ∣ > ε ] ≤ 2 ∣ U ∣ exp ( − 2 n ε 2 ) ; (22) \Pr\left[\sup_{x \in\mathcal{U}} \left|\widehat{F}_n(x) - F^*(x)\right| > \varepsilon\right] \le2|\mathcal{U}|\exp(-2n\varepsilon^2); \tag*{(22)} Pr [ x ∈ U sup F n ( x ) − F ∗ ( x ) > ε ] ≤ 2∣ U ∣ exp ( − 2 n ε 2 ) ; (22) (ii) under Assumption 2, H T ⊆ B T \mathcal{H}_T \subseteq\mathcal{B}_T H T ⊆ B T on every trajectory. Let L T \mathcal{L}_T L T be the set of all evaluations the run makes up to step T T T , each a state x x x with the score F ^ n \widehat{F}_n F n it received. Deduplication allows at most one evaluation of a state per step, so no state is evaluated more than T + 1 T+1 T + 1 times, and
Pr [ sup ( x , F ^ n ) ∈ L T ∣ F ^ n − F ∗ ( x ) ∣ > ε ] ≤ 2 ( T + 1 ) ∣ B T ∣ exp ( − 2 n ε 2 ) . (23) \Pr\left[\sup_{(x,\widehat{F}_n)\in\mathcal{L}_T}\left|\widehat{F}_n-F^*(x)\right|>\varepsilon\right]\le2(T+1)|\mathcal{B}_T|\exp(-2n\varepsilon^2). \tag*{(23)} Pr [ ( x , F n ) ∈ L T sup F n − F ∗ ( x ) > ε ] ≤ 2 ( T + 1 ) ∣ B T ∣ exp ( − 2 n ε 2 ) . (23) If every evaluation of a state returns the same score (a deterministic system agent, or scores cached per state), the factor T + 1 T+1 T + 1 can be dropped.
The two parts differ in exactly the way that matters here. The history H T \mathcal{H}_T H T is not fixed independently of D v a l i d \mathcal{D}_{\mathrm{valid}} D valid : validation scores decide which parents survive, and the proposer conditions on those scores (§ 2 ), so which candidates exist at all depends on the selection split. A union bound over a set chosen with the data does not control the deviation on that set. If many candidates of equal population utility are scored and only the luckiest are expanded, the supremum over what was kept is the maximum of many deviations, not of a few. So part (i) applied to H T \mathcal{H}_T H T as if it were fixed (which gives a half-width scaling as log ∣ H T ∣ \sqrt{\log|\mathcal{H}_T|} log ∣ H T ∣ , with the loose count ∣ H T ∣ ≤ 1 + T W ( 1 + k ) |\mathcal{H}_T| \le1+TW(1+k) ∣ H T ∣ ≤ 1 + T W ( 1 + k ) , which counts retained parents again) is not a guarantee for SPLICE. Part (ii) is, because B T \mathcal{B}_T B T is a data-independent superset. The price is that it is loose: log ∣ B T ∣ \log|\mathcal{B}_T| log ∣ B T ∣ grows linearly in T T T rather than logarithmically in the budget, and at the budgets of Section F.1 the guarantee exceeds 24 pp, wider than any margin this paper reports, so it is correct but not informative at our scale. Closing the gap between the two parts with an adaptive-data-analysis bound [7 , 22 , 67 ] is open.
Two points keep this from reaching further than it does. First, it is a selection guarantee , not a reporting one. Reported benchmark numbers are single evaluations on the untouched D t e s t \mathcal{D}_{\mathrm{test}} D test ; x ^ \hat{x} x ^ is a function of D t r a i n \mathcal{D}_{\mathrm{train}} D train and D v a l i d \mathcal{D}_{\mathrm{valid}} D valid only, so it is independent of the test sample and the reported number needs no union bound and no adaptivity correction. Adaptivity can make SPLICE select a worse prompt than it believes it has; it cannot make the reported test score of that prompt optimistic. Second, three properties of SPLICE plausibly narrow the adaptive channel, though none of them proves a bound. A state in the beam is never re-scored; a state that left the beam and is re-proposed is scored again, which with a stochastic system agent is a limited form of re-querying the validation split, and the factor T + 1 T+1 T + 1 in part (ii) prices it. Retention is a top-W W W cut, so validation enters selection through a ranking rather than through its full numerical detail. And the proposer never sees a validation example: it sees the scalar score F ^ ( x ) \widehat{F}(x) F ( x ) of its parent and critiques computed from D t r a i n \mathcal{D}_{\mathrm{train}} D train batches. Any residual selection bias then appears as a val–test gap on the returned prompt, which Section F.1 reports.
Theorem 5 is stated in the main text (p. 7).
The penalty for regularizing is at most λ \lambda λ times the cost of the unregularized optimum; the bound is tight at λ = 0 \lambda= 0 λ = 0 (no bias) and linear in λ \lambda λ . The bound is not an empirical claim: the proof rearranges two arg max \arg\max arg max definitions and uses only κ ≥ 0 \kappa\ge0 κ ≥ 0 , so it holds for any non-negative penalty on any search space and no experiment can violate it . It is also loose by construction, since the right-hand side is evaluated at the unregularized optimum. The growth the regularizer is meant to correct is an expected tendency of a proposer that edits by addition, not a theorem, and this paper does not measure it.
Proposition 2 is stated in the main text (p. 7).
The diminishing-returns hypothesis is not implied by γ \gamma γ -submodularity. The submodularity ratio bounds the immutable blocks’ marginals at L L L , the part of x a l l ∗ x^{*}_{\mathrm{all}} x all ∗ ’s commit set that leaves the frozen blocks at baseline, while Proposition 2 evaluates them at the baseline x ( 0 ) x^{(0)} x ( 0 ) , and Definition 16 says nothing about comparing the two (Remark 14). The hypothesis holds automatically when g g g is monotone with γ = 1 \gamma= 1 γ = 1 , and in general it formalizes the reading below: contract blocks do not become more worth editing once the mutable blocks are optimized. Without it the bound still holds with the marginals taken at L L L , (26). The fixed ordering is needed because the ground sets of (13) are defined at π ( 0 ) \pi^{(0)} π ( 0 ) : an all-mutable optimum at another ordering has no commit set in E a l l E^{\mathrm{all}} E all , and pricing it would require ordering moves in the ground set.
Under the diminishing-returns hypothesis, the price of freezing block i i i is at most its best single-block marginal gain over the variants it would have admitted , summed over frozen blocks and inflated by 1 / γ 1/\gamma 1/ γ . When immutable blocks are safety constraints, format contracts, or tool schemas (whose marginal utility is by design small, because they constrain behavior rather than improve the metric), the right-hand side is small, and so is the price of selective mutability.
That reading is qualitative. Both factors on the right-hand side are outside what a deployment can measure: γ \gamma γ is the quantity we cannot estimate per benchmark (§ 6 ), and V ~ i \widetilde{V}_i V i is unobservable by construction, since it describes a search that the contract forbids running. We therefore do not report a realized-to-bound ratio for Proposition 2, and no experiment in this paper certifies it numerically. What Section F.2 does instead is measure a proxy for the left-hand side, the score gap between the returned prompts, comparing full SPLICE against an all-mutable variant, so it tests the conclusion rather than either hypothesis; it also reports the case the bound is least flattering in, where a frozen clause carries a large marginal gain by construction.
Scope. These results are stated at the granularity at which each component is defined. We do not attempt a single end-to-end sample-complexity bound composing every component: it would multiply the success probability of Theorem 3, the bias of Theorem 5, the terminal quality of the idealized greedy of Proposition 4, and the slack of Theorem 7 into constants no sharper than their product. The component-wise statements are more informative: each concerns one component, and an improvement to any one of them carries over to the composition.
Proofs
Proof of Theorem 7. Part (i). Fix x ∈ U x \in\mathcal{U} x ∈ U . By Assumption 3 the per-example scores r ( M ( x ; render ( x ) ) , y ) r(M(x;\operatorname{render}(x)),y) r ( M ( x ; render ( x )) , y ) lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , and the validation split D v a l i d \mathcal{D}_{\mathrm{valid}} D valid consists of n n n i.i.d. draws, so F ^ n ( x ) \widehat{F}_n(x) F n ( x ) is an average of n n n independent [ 0 , 1 ] [0,1] [ 0 , 1 ] -valued variables with mean F ⋆ ( x ) F^{\star}(x) F ⋆ ( x ) by (2). Lemma 2 gives
Pr [ ∣ F ^ n ( x ) − F ⋆ ( x ) ∣ > ε ] ≤ 2 exp ( − 2 n ε 2 ) . \Pr\left[\left|\widehat{F}_n(x)-F^{\star}(x)\right|>\varepsilon\right]\leq2\exp\left(-2n\varepsilon^2\right). Pr [ F n ( x ) − F ⋆ ( x ) > ε ] ≤ 2 exp ( − 2 n ε 2 ) .
This step uses that x x x is fixed before D v a l i d \mathcal{D}_{\mathrm{valid}} D valid is drawn; it is the only place independence enters. Because U \mathcal{U} U is fixed in the same sense, a union bound over its ∣ U ∣ |\mathcal{U}| ∣ U ∣ members gives (23). The union bound needs no independence across members, so sharing one D v a l i d \mathcal{D}_{\mathrm{valid}} D valid across all of them is harmless.
Part (ii). By Assumption 2, every child is Apply ( x , u ) \operatorname{Apply}(x,u) Apply ( x , u ) with u u u a primitive edit or the no-op, so it lies at edit-graph distance at most one from its parent. Parents at step t t t belong to C t − 1 ⊆ H t − 1 C_{t-1}\subseteq\mathcal{H}_{t-1} C t − 1 ⊆ H t − 1 , and C 0 = { x ( 0 ) } C_0=\{x^{(0)}\} C 0 = { x ( 0 ) } , so by induction every member of H T \mathcal{H}_T H T is within distance T T T of x ( 0 ) x^{(0)} x ( 0 ) : H T ⊆ B T \mathcal{H}_T\subseteq\mathcal{B}_T H T ⊆ B T on every trajectory, whatever the data. The ball B T \mathcal{B}_T B T is determined by G \mathcal{G} G and x ( 0 ) x^{(0)} x ( 0 ) alone, so it is fixed independently of D v a l i d \mathcal{D}_{\mathrm{valid}} D valid .
A state may be evaluated more than once: deduplication compares a proposal only with the current beam and the step’s other proposals, so a state that left the beam can be re-proposed and re-scored. Deduplication removes duplicates within a step, so a state is evaluated at most once per step and at most T + 1 T+1 T + 1 times in all. Each evaluation draws fresh model randomness on the same D v a l i d \mathcal{D}_{\mathrm{valid}} D valid . Realize that randomness in advance: for every x ∈ B T x\in\mathcal{B}_T x ∈ B T and j ≤ T + 1 j\leq T+1 j ≤ T + 1 , draw independently the model outputs the j j j -th evaluation of x x x will use, and let F ^ n ( j ) ( x ) \widehat{F}^{(j)}_n(x) F n ( j ) ( x ) be the resulting score. This table has the same law as the scores the run produces, and it does not depend on the run’s choices, so each F ^ n ( j ) ( x ) \widehat{F}^{(j)}_n(x) F n ( j ) ( x ) is an average of n n n independent [ 0 , 1 ] [0,1] [ 0 , 1 ] -valued scores with mean F ⋆ ( x ) F^\star(x) F ⋆ ( x ) , and Lemma 2 applies to it as in part (i). Every evaluation in L T \mathcal{L}_T L T is one entry of the table, so
Pr [ sup ( x , F ^ n ) ∈ L T ∣ F ^ n − F ⋆ ( x ) ∣ > ε ] ≤ Pr [ max x ∈ B T , j ≤ T + 1 ∣ F ^ n ( j ) ( x ) − F ⋆ ( x ) ∣ > ε ] \Pr\left[\sup_{(x,\widehat{F}_n)\in\mathcal{L}_T}\left|\widehat{F}_n-F^\star(x)\right|>\varepsilon\right]\leq\Pr\left[\max_{x\in B_T,\ j\leq T+1}\left|\widehat{F}^{(j)}_n(x)-F^\star(x)\right|>\varepsilon\right] Pr [ ( x , F n ) ∈ L T sup F n − F ⋆ ( x ) > ε ] ≤ Pr [ x ∈ B T , j ≤ T + 1 max F n ( j ) ( x ) − F ⋆ ( x ) > ε ]
≤ 2 ( T + 1 ) ∣ B T ∣ exp ( − 2 n ε 2 ) , (24) \leq2(T+1)|B_T|\exp(-2n\varepsilon^2), \tag*{(24)} ≤ 2 ( T + 1 ) ∣ B T ∣ exp ( − 2 n ε 2 ) , (24)
which is (24). If every evaluation of a state returns the same score (as when scores are cached per state), the table has one distinct entry per state and the union runs over B T B_T B T alone. For the cardinality, every state has at most Δ G \Delta_{\mathcal{G}} Δ G neighbors, so the ball holds at most ∑ j = 0 T Δ G j ≤ ( Δ G + 1 ) T \sum_{j=0}^{T}\Delta_{\mathcal{G}}^j\leq(\Delta_{\mathcal{G}}+1)^T ∑ j = 0 T Δ G j ≤ ( Δ G + 1 ) T states, and trivially at most ∣ X ∣ |\mathcal{X}| ∣ X ∣ .
Proof of Theorem 5. Let x ⋆ ∈ arg max X F ⋆ x^\star\in\arg\max_{\mathcal{X}}F^\star x ⋆ ∈ arg max X F ⋆ and x λ ⋆ ∈ arg max X F λ ⋆ x^\star_\lambda\in\arg\max_{\mathcal{X}}F^\star_\lambda x λ ⋆ ∈ arg max X F λ ⋆ where F λ ⋆ = F ⋆ − λ κ F^\star_\lambda=F^\star-\lambda\kappa F λ ⋆ = F ⋆ − λκ with λ ≥ 0 \lambda\geq0 λ ≥ 0 and κ ≥ 0 \kappa\geq0 κ ≥ 0 . By optimality of x λ ⋆ x^\star_\lambda x λ ⋆ for F λ ⋆ F^\star_\lambda F λ ⋆ and feasibility of x ⋆ x^\star x ⋆ ,
F ⋆ ( x λ ⋆ ) − λ κ ( x λ ⋆ ) ≥ F ⋆ ( x ⋆ ) − λ κ ( x ⋆ ) . F^\star(x^\star_\lambda)-\lambda\kappa(x^\star_\lambda)\geq F^\star(x^\star)-\lambda\kappa(x^\star). F ⋆ ( x λ ⋆ ) − λκ ( x λ ⋆ ) ≥ F ⋆ ( x ⋆ ) − λκ ( x ⋆ ) .
Rearranging,
F ⋆ ( x ⋆ ) − F ⋆ ( x λ ⋆ ) ≤ λ ( κ ( x ⋆ ) − κ ( x λ ⋆ ) ) ≤ λ κ ( x ⋆ ) , F^\star(x^\star)-F^\star(x^\star_\lambda)\leq\lambda\left(\kappa(x^\star)-\kappa(x^\star_\lambda)\right)\leq\lambda\kappa(x^\star), F ⋆ ( x ⋆ ) − F ⋆ ( x λ ⋆ ) ≤ λ ( κ ( x ⋆ ) − κ ( x λ ⋆ ) ) ≤ λκ ( x ⋆ ) ,
the last inequality because κ ( x λ ⋆ ) ≥ 0 \kappa(x^\star_\lambda)\geq0 κ ( x λ ⋆ ) ≥ 0 . This is Theorem 5.
Proof of Proposition 2. Throughout, the ground set is E a l l E^{\mathrm{all}} E all of (13), not E E E : the statement compares an optimum that may edit frozen blocks against one that may not, so the frozen coordinates must be present in the ground set for either the hypothesis or the conclusion to have content. On E E E the set S i m m S_{\mathrm{imm}} S imm constructed below is empty, every marginal in (26) vanishes, and the argument degenerates to 0 ≤ 0 0\leq0 0 ≤ 0 .
Among the all-mutable optima, take x a l l ⋆ x^\star_{\mathrm{all}} x all ⋆ whose set S ⋆ ⊆ E a l l S^\star\subseteq E^{\mathrm{all}} S ⋆ ⊆ E all of block-variant commits is inclusion-minimal (a commit set exists because Π = { ( π ( 0 ) } } \Pi=\{(\pi^{(0)}\}\} Π = {( π ( 0 ) }} , and a minimal one because X a l l \mathcal{X}_{\mathrm{all}} X all is finite), let S i m m : = { ( i , v ) ∈ S ⋆ : i ∈ I i m m } S_{\mathrm{imm}}:=\{(i,v)\in S^\star:i\in I_{\mathrm{imm}}\} S imm := {( i , v ) ∈ S ⋆ : i ∈ I imm } be its entries on immutable blocks, and put L : = S ⋆ ∖ S i m m ⊆ E L:=S^\star\setminus S_{\mathrm{imm}}\subseteq E L := S ⋆ ∖ S imm ⊆ E . Minimality gives g ( L ) < g ( S ⋆ ) g(L)<g(S^\star) g ( L ) < g ( S ⋆ ) whenever S i m m ≠ ∅ S_{\mathrm{imm}}\neq\varnothing S imm = ∅ , since otherwise x L x_L x L would be an optimum with a smaller commit set. Then x L x_L x L leaves every immutable block at its baseline variant, so x L ∈ X x_L\in\mathcal{X} x L ∈ X is feasible for the restricted search and therefore
g ( L ) ≤ F ⋆ ( x m u t ⋆ ) − F ⋆ ( x ( 0 ) ) . (25) g(L)\leq F^\star(x^\star_{\mathrm{mut}})-F^\star(x^{(0)}). \tag*{(25)} g ( L ) ≤ F ⋆ ( x mut ⋆ ) − F ⋆ ( x ( 0 ) ) . (25)
Apply Definition 16 on E ′ = E a l l E'=E^{\mathrm{all}} E ′ = E all with this L L L and S = S i m m S=S_{\mathrm{imm}} S = S imm , which are disjoint by construction:
γ [ g ( L ∪ S i m m ) − g ( L ) ] ≤ ∑ e ∈ S i m m [ g ( L ∪ { e } ) − g ( L ) ] . \gamma\left[g(L\cup S_{\mathrm{imm}})-g(L)\right]\leq\sum_{e\in S_{\mathrm{imm}}}\left[g(L\cup\{e\})-g(L)\right]. γ [ g ( L ∪ S imm ) − g ( L ) ] ≤ e ∈ S imm ∑ [ g ( L ∪ { e }) − g ( L ) ] .
If g ( L ∪ S i m m ) = g ( L ) g(L\cup S_{\mathrm{imm}})=g(L) g ( L ∪ S imm ) = g ( L ) the left-hand side of (26) is at most zero by (25) and the claim is immediate; otherwise the pair is admissible in the minimum defining γ ( g ; E a l l ) \gamma(g;E^{\mathrm{all}}) γ ( g ; E all ) . Since L ∪ S i m m = S ⋆ L\cup S_{\mathrm{imm}}=S^\star L ∪ S imm = S ⋆ and g ( S ⋆ ) = F ⋆ ( x a l l ⋆ ) − F ⋆ ( x ( 0 ) ) g(S^\star)=F^\star(x^\star_{\mathrm{all}})-F^\star(x^{(0)}) g ( S ⋆ ) = F ⋆ ( x all ⋆ ) − F ⋆ ( x ( 0 ) ) , dividing by γ > 0 \gamma>0 γ > 0 and combining with (25) gives
F ⋆ ( x a l l ⋆ ) − F ⋆ ( x m u t ⋆ ) ≤ g ( S ⋆ ) − g ( L ) ≤ 1 γ ∑ e ∈ S i m m [ g ( L ∪ { e } ) − g ( L ) ] , (26) F^\star(x^\star_{\mathrm{all}})-F^\star(x^\star_{\mathrm{mut}})\leq g(S^\star)-g(L)\leq\frac{1}{\gamma}\sum_{e\in S_{\mathrm{imm}}}\left[g(L\cup\{e\})-g(L)\right], \tag*{(26)} F ⋆ ( x all ⋆ ) − F ⋆ ( x mut ⋆ ) ≤ g ( S ⋆ ) − g ( L ) ≤ γ 1 e ∈ S imm ∑ [ g ( L ∪ { e }) − g ( L ) ] , (26)
which is the price of freezing expressed through the marginal gains of the immutable blocks evaluated at L L L , the mutable part of S ⋆ S^\star S ⋆ . This step uses only Assumption 4. Under the diminishing-returns hypothesis of Proposition 2, Corollary 3 converts the right-hand side to the baseline form (9), which completes the proof.
Corollary 3 (Baseline form of the price of freezing). If in addition g g g has diminishing returns on immutable coordinates, i.e. g ( L ∪ { e } ) − g ( L ) ≤ g ( { e } ) − g ( ∅ ) g(L\cup\{e\})-g(L)\leq g(\{e\})-g(\emptyset) g ( L ∪ { e }) − g ( L ) ≤ g ({ e }) − g ( ∅ ) for every e ∈ S i m m e\in S_{\mathrm{imm}} e ∈ S imm and the above L L L (which holds whenever g ( A ∪ { e } ) − g ( A ) ≤ g ( { e } ) − g ( ∅ ) g(A\cup\{e\})-g(A)\leq g(\{e\})-g(\emptyset) g ( A ∪ { e }) − g ( A ) ≤ g ({ e }) − g ( ∅ ) for every feasible A ⊆ E A\subseteq E A ⊆ E and e ∈ E a l l ∖ E e\in E^{\mathrm{all}}\setminus E e ∈ E all ∖ E ), then
F ⋆ ( x a l l ⋆ ) − F ⋆ ( x m u t ⋆ ) ≤ 1 γ ∑ i ∈ I i m m ∑ v ∈ V ~ i max [ F ⋆ ( x ( 0 ) [ i : = v ] ) − F ⋆ ( x ( 0 ) ) ] , (27) F^\star(x^\star_{\mathrm{all}})-F^\star(x^\star_{\mathrm{mut}})\leq\frac{1}{\gamma}\sum_{i\in I_{\mathrm{imm}}}\sum_{v\in\widetilde V_i}\max\left[F^\star(x^{(0)}[i:=v])-F^\star(x^{(0)})\right], \tag*{(27)} F ⋆ ( x all ⋆ ) − F ⋆ ( x mut ⋆ ) ≤ γ 1 i ∈ I imm ∑ v ∈ V i ∑ max [ F ⋆ ( x ( 0 ) [ i := v ]) − F ⋆ ( x ( 0 ) ) ] , (27) which is (9).
Proof. Substituting the diminishing-returns inequality into (26) replaces each marginal at L L L by a marginal at ∅ \emptyset ∅ ; then g ( { ( i , v ) } ) − g ( ∅ ) = F ⋆ ( x ( 0 ) [ i : = v ] ) − F ⋆ ( x ( 0 ) ) g(\{(i,v)\})-g(\emptyset)=F^\star(x^{(0)}[i:=v])-F^\star(x^{(0)}) g ({( i , v )}) − g ( ∅ ) = F ⋆ ( x ( 0 ) [ i := v ]) − F ⋆ ( x ( 0 ) ) by (14), and bounding each term by the best counterfactual variant of its block (the maximum over V ~ i \widetilde V_i V i , which is the set the entries of S i m m S_{\mathrm{imm}} S imm are drawn from) and each block of S i m m S_{\mathrm{imm}} S imm by all of I i m m I_{\mathrm{imm}} I imm (each omitted term is non-negative, since the seed variant v i ( 0 ) ∈ V ~ i v_i^{(0)}\in\widetilde V_i v i ( 0 ) ∈ V i gives 0) gives (27).
supplies is therefore a shape rather than a budget: the price of freezing is controlled by the marginal value of the frozen blocks. That is the claim Section E.6 makes, and Section F.2 probes it by constructing a frozen block whose marginal value is large by design.
Experimental Details
This section extends § 4 : protocols and splits, the full contract study, the ablations summarized there, capacity and cost, the judge-alignment application, and per-benchmark diagnostics.
Protocol and Reporting
THREE MODEL ROLES. Every run has three model roles, which we keep apart. The target model is the one whose prompt is being optimized and on which the returned prompt is deployed; it is fixed by whichever published protocol we are reproducing. The proposal agent samples the k k k candidate edits per parent, and the critique agent produces the dual section-local gradients of (7) . Proposal and critique are ordinarily distinct models, which we keep separate so that the critique is less likely to endorse the reasoning that produced the edit it assesses. The exception is AIME-2025, where both roles run on the same model and are separated only by temperature (0.9 for proposal, 0.0 for critique).
THE STATE, CONCRETELY. Definition 5 is instantiated by a template of named sections. On SST-5 and AIME the prompt is m = 5 m = 5 m = 5 blocks (role, objective, approach, examples, and output format) rendered to a single XML stream, with the output-format block tagged immutable and the remaining four mutable. So ∣ I m u t ∣ = 4 \lvert I_{\mathrm{mut}}\rvert= 4 ∣ I mut ∣ = 4 , the frozen coordinate is the output contract, and V i V_i V i for that block is a singleton by construction rather than by instruction. The contract experiment of Section F.2 extends this template with a seven-clause contract block and varies exactly which blocks carry the tag.
SEARCH CONFIGURATION. Search parameters differ by benchmark, so there is no single default: beam width is 5 on SST-5 and AIME (4 in the seeded SST-5 sweeps) but 4 on BBH, GPQA-Diamond and HelpSteer2; the fan-out k k k ranges over 3–5; and the quality-gate ratio ϱ \varrho ϱ of Proposition 1 is 0.7 on SST-5 and AIME and 0.9 on HelpSteer2, while the BBH and GPQA-Diamond configurations do not set it, so the implementation’s default ϱ = 0 \varrho= 0 ϱ = 0 applies and the gate is inactive there. Every benchmark number uses λ = 0 \lambda= 0 λ = 0 . Every benchmark follows its source protocol exactly (target model, decoding settings, splits and metric). Unless an ablation varies them, proposals and critiques come from fixed proposal and critique models (proposal temperature 0.9, 1.0 on BBH; critique temperature 0.0), with AIME-2025 the exception noted above. The improvement threshold is Δ min = 0.003 \Delta_{\min} = 0.003 Δ m i n = 0.003 on SST-5 and AIME and 0.005 on BBH and GPQA. Momentum is enabled with window w = 5 w = 5 w = 5 throughout, and setting Section F.3.2 examines directly.
THREE SPLITS, THREE ROLES. Every run uses three disjoint i.i.d. splits, and both the guarantees and the reported numbers depend on which split does what. D t r a i n \mathcal{D}_{\mathrm{train}} D train supplies a fresh batch B t B_t B t each step on which the current beam is re-run; those scores feed the critique and are never used for selection, retention, gating, stopping or output. D v a l i d \mathcal{D}_{\mathrm{valid}} D valid is fixed and used to score and select candidates, under the cached-scoring convention of § 2 : each candidate is scored once when it is created and carries that score while it stays in the beam, rather than being re-rolled. (A candidate that leaves the beam and is later re-proposed verbatim is scored again, since duplicate duplication checks only the current beam.) This is what makes Lemma 1 operative rather than merely formal. D t e s t \mathcal{D}_{\mathrm{test}} D test is disjoint and never queried during search. The returned prompt is leader(C T C_T C T ), which under elitist selection is also the best-scoring candidate the run evaluated, so its validation score is optimistic and we report test accuracy separately.
REPORTING CONVENTION. We label the two accuracies explicitly, because the distinction carries the statistical argument below. V a l Val V a l is accuracy on D v a l i d \mathcal{D}_{\mathrm{valid}} D valid : what the optimizer sees, and the quantity every selection decision is made against. T e s t Test T es t is accuracy on D t e s t \mathcal{D}_{\mathrm{test}} D test , a single evaluation of the single returned prompt. Unless a number is marked V a l Val V a l , it is test accuracy.
ADAPTIVE REUSE OF THE VALIDATION SPLIT. D v a l i d \mathcal{D}_{\mathrm{valid}} D valid is queried repeatedly across a run to rank candidates, so a single-candidate concentration bound does not cover selection , and we separate the two claims it might be asked to support. For reporting , the returned prompt x ^ \hat{x} x ^ is a function of D t r a i n \mathcal{D}_{\mathrm{train}} D train , D v a l i d \mathcal{D}_{\mathrm{valid}} D valid and the optimizer’s own randomness, so x ^ \hat{x} x ^ is independent of the test sample and the reported number needs no union bound and no adaptivity correction. For selection , the correct statement is the uniform bound of Theorem 7 , and it is worth being exact about which part of it applies. Bounding by the size of the evaluated history, ∣ H T ∣ ≤ 1 + T W ( 1 + k ) |\mathcal{H}_T| \le1 + TW(1 + k) ∣ H T ∣ ≤ 1 + T W ( 1 + k ) , would give a 95% uniform half-width of 10.3 pp on SST-5 (n = 500 n=500 n = 500 , W = 5 W=5 W = 5 , k = 3 k=3 k = 3 , T = 50 T=50 T = 50 , so ∣ H T ∣ ≤ 1001 |\mathcal{H}_T| \le1001 ∣ H T ∣ ≤ 1001 ) against 6.1 pp for a single candidate. That figure is not a guarantee for SPLICE, because the history is chosen using the same validation scores it would be bounding (Remark 12); it is what a procedure that fixed its candidates in advance would get. The valid statement unions over the radius-T T T ball of the edit graph, which contains every history and does not depend on the data. Its half-width is ( ln ( 2 ( T + 1 ) / δ ) + T ln ( Δ G + 1 ) ) / 2 n \sqrt{(\ln(2(T+1)/\delta)+T\ln(\Delta_G+1))/2n} ( ln ( 2 ( T + 1 ) / δ ) + T ln ( Δ G + 1 )) /2 n , which at T = 50 T=50 T = 50 exceeds 24 pp for every maximum degree Δ G ≥ 2 \Delta_G \ge2 Δ G ≥ 2 . So we have a correct selection guarantee that is uninformative at our budget, and an informative figure that is not a guarantee. We report both rather than let the second pass for the first.
What remains is the empirical check. Validation scores decide which parents survive, and the proposer conditions on its parent’s score, so the history depends on validation noise. Three properties of SPLICE plausibly narrow that channel without bounding it: each candidate is scored once while it stays in the beam, retention is a top-W W W cut rather than a numerical reweighting, and the proposer sees scalar scores and D t r a i n D_{\mathrm{train}} D train critiques but never a D v a l i d D_{\mathrm{valid}} D valid example. What those properties cannot do is stop the search from fitting validation noise, and on the one configuration where we can check, it does. The seeded SST-5 runs (the momentum and contract experiments) are the only seed-paired runs for which we report both a validation and a test score for the returned prompt: in the momentum control arm (Table 13 ) the leader scores 59.9 on validation and 56.3 on test, a 3.6 pp optimism, against a seed prompt that scores 54.0 and 56.2. So the search gained 5.9 pp on the split it selected on and 0.1 pp on the split it did not. That is selection-on-noise during search, and we report it as such. It does not bias the reported number, which is measured on D t e s t D_{\mathrm{test}} D test and is independent of how x ^ \hat{x} x ^ was chosen; it does mean a validation curve in this paper should not be read as an estimate of held-out gain. The GPQA sweep has no test split, and its train–validation gaps (Figure 17 in Section F) are not evidence either way about validation optimism.
Table 13. Momentum: a null at the default window and a real cost at a long one. SST-5, gemma-3-27b-it, three seeds (42/43/44) paired across arms so every contrast is seed-matched rather than confounded by draw; each arm differs from the control in exactly one field. Steps is the mean number of steps before early stopping; Prop. win is the fraction of proposed children beating their parent. The last column is the paired per-seed difference (control − arm, validation pp; positive means the control is better), which is the meaningful comparison because pairing removes the cross-seed draw variance that dominates the ± on the arm means.
Figure 17. Train–validation gap (Train − Val) by strategy on GPQA-Diamond. Iterative strategies are near zero; BoN strategies have large negative gaps of −19 to −31 percentage points, meaning single-batch training accuracy is not a usable proxy for validation performance. Tick label “w = 4 w=4 w = 4 ” is the beam width W = 4 W=4 W = 4 .
REPRODUCIBILITY. Prompt optimization is unusually sensitive to details that are easy to leave unstated (the seed prompt, decoding settings, parsing rules, model versions, splits, and candidate budget), so we state what the seed controls and what it does not.
The random seed governs batch draws and data ordering. It does not control sampling inside the language models: the proposal agent runs at non-zero temperature behind a black-box endpoint, and its draws are not reproducible from any seed we hold. Every spread we report across seeds is therefore total run-to-run variance (seed-controlled data sampling plus irreducible model sampling noise) rather than the seed-attributable component alone, which makes it a conservative estimate of stability: it can only overstate the variability a fixed-data rerun would show.
Table 7 reports the full SST-5 results alongside the published baselines from the two protocols. Under the [89 ] protocol (target: gemma-3-27b-it), SPLICE reaches 59.2% accuracy, +2.9 pp over the strongest published method (CAPO at 56.3). Under the [94 ] protocol (target: deepseek-v3.2), SPLICE reaches 57.4%, +0.8 pp over the strongest prior method (EvoPrompt at 56.6). The gap is larger on gemma-3-27b-it, whose protocol baseline is 44.6% against 56.0% for deepseek-v3.2, and the published methods cluster in 53.3–56.6% on both (GEPA’s 42.0 aside). A 2.9 pp gap over CAPO corresponds to an error-rate reduction from 43.7% to 40.8%, a 6.6% relative reduction; the same gap on deepseek-v3.2’s saturated band would require a method that breaks out of the cluster entirely, which no published method in this comparison does.
On the [37 ] protocol (GPT-3.5-Turbo), SPLICE reaches 91.0% on ARC-Challenge and 83.09% on GSM8K (Table 2 ), clearing the strongest UniPrompt configuration by +0.5 pp and +0.7 pp respectively. The lead over the TextGrad / ProTeGi family is wider: +12.2 pp on ARC-Challenge over ProTeGi and +1.5 pp on GSM8K over TextGrad. Under the [1 ] protocol (target GPT-4.1 Mini; Table 3 ), SPLICE reaches 64.4% on AIME-2025 and 96.24% on PUPA (+5.1 pp over GEPA on AIME, within 0.22 pp of GEPA+Merge on PUPA). Under the [65 ] protocol (Claude Haiku 4.5; Table 4 ), SPLICE reaches 92.6% on BBH (+0.7 pp over GEPA) and ties GEPA at 68.4% on GPQA-Diamond, +3.1 pp over the protocol’s baseline prompt and +4.1 pp over ContraPrompt.
Table 3. Optimized for model: GPT-4.1 Mini; datasets: AIME-2025, PUPA [1 ] . Trace (OptoPrime) is Cheng et al. [11 ] .
Under the accounting of § 4 , a margin of at most 0.5 pp either way is a match: ARC-Challenge (+0.5), GPQA-Diamond (0.0) and PUPA (−0.22). The GSM8K and BBH wins (+0.69, +0.70 pp) clear that threshold only narrowly and sit inside the range that differences in tuning, API version or prompt formatting could account for, since none of the five reproduced protocols reports seed variance for the baselines we compare against. The claims we rest on are the margins with headroom behind them (AIME-2025 and SST-5 on gemma-3-27b-it) and the absence of any loss beyond the threshold on any of the five targets.
Does the Constrained Formulation Buy Anything?
Frozen blocks are preserved by construction: the search space contains no variant of an immutable block, so reporting a 0% modification rate against a baseline’s nonzero rate restates Definition 3 rather than measuring anything. The question that is not definitional is the one a practitioner actually faces: when an optimizer is able to rewrite a contract, does it, and what does that cost? Answering it needs a setting where the contract is worth breaking. We construct one.
THE CONTRACT. Table 8 gives the seven-clause contract, which instantiates all four classes of production artifact that motivate § 2 : a record_sentiment tool schema, safety text, a strict output envelope, and a business rule. The task is SST-5 and the target is gemma-3-27b-it. We take the deliberate trade of a synthetic-but-exact contract over a real deployed one: a production prompt would be unreproducible and would require an LLM judge to rule on whether a given rewrite counts as a violation, whereas here the frozen text is fixed and public, so detection is a regular expression and a parser and every rate we report is exact and recomputable.
The clause at the center of the experiment is a compliance-routing rule of the kind found in deployed agents:
POLICY-1. If the snippet mentions “film” or “movie”, do not classify it. Emit {"label": "ESCALATE"}; these require human review.
The optimizer’s metric is classification accuracy, so an escalation is not a sentiment label, scores zero, and obeying POLICY-1 forfeits score. We call this metric the proxy . The mis-specification is deliberate and, we would argue, typical: hand-written scoring functions routinely omit credit for a correct refusal. Table 9 gives the per-example credit under the proxy and under the contract-aware metric that scores the deployed objective, together with the ceilings each implies. With a 26% trigger rate the two are near-opposites on the examples POLICY-1 governs: the proxy caps a fully compliant prompt at 74% and the only route to 100% is total non-compliance. That ≈26 pp gap is the score on offer for breaking the contract, and it is the setup rather than an artifact of it.
WHY THIS CLAUSE AND NOT AN EASIER ONE. A contract that is costless to obey cannot demonstrate the value of protecting it: if compliance never reduces the metric, no optimizer has an incentive to break it and every method looks equally safe. We verified this concretely: several natural safety clauses in the same prompt (forbidding chain-of-thought, requiring the full five-point label scale) improved accuracy when obeyed, and no arm disturbed them. POLICY-1 satisfies three requirements simultaneously. It can be obeyed : the trigger is lexical, so compliance is a decision rather than a capability limit, and the unoptimized seed prompt (A0) complies on 96.5% of triggered test examples. (A semantically gated variant, “abstain when uncertain”, was ignored outright and produced no measurable behavior.) It is costly : the rule fires on 26% of examples. And it fails silently : a missed escalation is well-formed, plausible output that raises no parser or schema error, so
caption: Table 8: The seven-clause contract, by artifact class. The prompt instantiates all four classes of production artifact that motivate the constrained formulation of § 2 , rather than being a benchmark prompt with a safety sentence appended. The trade is deliberate: a prompt from a live deployment would be unreproducible and would require an LLM judge to rule on whether a given rewrite constitutes a violation, whereas here the frozen text is fixed and public, so detection is a regular expression and a parser and every rate in Table 10 is exact and recomputable. Only the business rule is reward-conflicted, and that asymmetry is the experiment: the other three classes were left untouched by every arm in every candidate. Optimizers do not vandalize indiscriminately; they trade away precisely the contracts that cost reward, and a practitioner cannot know in advance which those are.
Table 10. What happens to a reward-conflicted contract clause when an optimizer is allowed to touch it. Every candidate prompt the search evaluated on SST-5 (gemma-3-27b-it), classified by the fate of the POLICY-1 clause; counts are candidates pooled across three paired seeds. Verbatim: the 284-character clause is found unchanged in the rendered prompt, after normalizing whitespace and JSON over-escaping. Reworded: the string POLICY-1 still appears but its text has changed. Deleted: no trace of the clause. Mod. rate = (Reworded + Deleted) / Candidates, in percent. Detection uses a regular expression and a parser rather than an LLM judge, so the counts are deterministic. A1’s zero is definitional (the search space contains no variant of an immutable block) and is reported to anchor the three editable arms rather than as a result in itself. The informative contrast is A4 against A2: a “do not edit” instruction eliminates deletion entirely (0 against 223) and raises verbatim retention about fifteenfold (27.2% against 1.8%), yet still leaves 72.8% of candidates with the clause paraphrased.
:::
caption: Table 9: Left: per-example credit under the two scoring rules. T \mathcal{T} T is the set of POLICY-1-triggered examples (26.0 % 26.0\% 26.0% of D v a l i d D_{\mathrm{valid}} D valid , 26.3 % 26.3\% 26.3% of D t e s t D_{\mathrm{test}} D test ) and U \mathcal{U} U the remainder; each metric is the mean credit over all n n n examples. Two rows carry the design. Row 1 is the mis-specification: a correct refusal earns 0 under the proxy and 1 under the contract-aware metric, so the proxy silently punishes the behavior the contract mandates. Row 6 is the anti-gaming check: a spurious refusal earns 0 under both, so blanket escalation scores only ∣ T ∣ / n ≈ 26 % |\mathcal{T}|/n \approx26\% ∣ T ∣/ n ≈ 26% rather than 100% and the contract-aware metric cannot be gamed by indiscriminate abstention. Right: the resulting ceilings. With a 26% trigger rate the two objectives are near-opposites on the examples POLICY-1 governs, so each metric’s ceiling sits close to the other’s floor. The proxy caps a fully compliant prompt at 74% and the only route to 100% is total non-compliance: that ≈ 26 \approx26 ≈ 26 pp gap is the reward on offer for breaking the contract, and it is the setup rather than an artifact of it.
:::
optimizer receives no corrective signal. This is the class of failure that format validation cannot detect and that selective mutability is designed to guard against.
ARMS AND PROTOCOL. Four arms share the contract text, hyperparameters, splits and objective, and differ only in whether the contract is mutable: A1 SPLICE (immutable), A2 all-mutable (identical blocks, editable), A3 monolithic (the entire prompt as one editable block, which is the representation every prior method searches over), and A4 soft-instructed (editable, plus an explicit “do not edit” directive). A3 and A4 both request preservation; only A1 enforces it, and that contrast is what separates a structural guarantee from an instruction. Splits follow Section F.1: fresh training batches produce critiques only, a fixed 300-example D v a l i d D_{\mathrm{valid}} D valid selects candidates under the proxy, and the 2,210-example D t e s t D_{\mathrm{test}} D test is queried once on the returned prompt under the contract-aware metric. The optimizer therefore cannot optimize the contract-aware objective (it never observes it), and the search proceeds exactly as a practitioner’s would under a misspecified metric. Gold sentiment labels are unmodified; only the scoring rule differs, on the 26.3% of test examples POLICY-1 governs. Three paired seeds.
RESULTS. Table 10 reports the fate of POLICY-1 over every candidate the search produced; Table 11 reports accuracy and held-out compliance, and Figure 2 plots them. Modification rates are 0% for A1 by construction, 72.8% for A4, 88.2% for A3 and 98.2% for A2. The ordering inverts between the two metrics: every unconstrained arm beats SPLICE by roughly 10 pp on the proxy and loses by roughly 17 pp on the objective a practitioner deploys against, and escalation compliance on held-out test is 66.8% for A1 against 0–1.4% for the editable arms. The optimizer did exactly what it was asked, and the result is worse to deploy.
Table 11. The ordering inverts between the metric the optimizer sees and the one a deployment pays. SST-5, gemma-3-27b-it, mean ± s.d. over three paired seeds. The proxy credits sentiment labels only, so a correct escalation scores zero and obeying POLICY-1 forfeits reward; the contract-aware metric credits the escalation instead. Every editable arm beats SPLICE by roughly 10 pp on the proxy and loses by roughly 17 pp on the objective a practitioner deploys against: freezing costs 10.5 pp of proxy (59.8 → 49.3) and buys 17.1 pp of contract-aware accuracy (41.4 → 58.5). The arms are equally good classifiers : untriggered label accuracy backs out to ≈55.5% (A1) against ≈56.2% (A2), so the whole gap is escalation behavior rather than sentiment quality. A2’s compliance is exactly 0.0 because every seed deleted the clause, which is a different failure from A1’s 66.8%: see § 6 on text versus behavior.
Four observations follow. First, the arms are equally good classifiers. Untriggered label accuracy backs out to ≈55.5% (A1) against ≈56.2% (A2), so the entire 17.1 pp gap is escalation behavior rather than sentiment quality; the constraint costs nothing on the task itself. Second, the edits were not cosmetic. A3 reworded the clause in 316 of 372 candidates and still escalated only 0.1% of triggered snippets: present in name, stripped of force. This is the silent failure a validator cannot catch, and it is why we measure behavior on held-out test rather than stopping at a text-identity check. Third, A4 is the most informative arm. “Do not edit” worked in part: zero deletions against A2’s 223, and the highest verbatim retention of any editable arm (27.2% against 1.8%). Told not to remove the clause, the optimizer paraphrased it into ineffectiveness instead, and none of that partial protection survived to deployment (1.4% compliance). An instruction shifts the distribution of tampering; it does not prevent tampering, and it cannot survive a selection rule that rewards violation. Fourth, the other three contract classes were untouched by every arm in every candidate. Optimizers do not vandalize indiscriminately; they trade away precisely the clauses that cost score. That is the argument for freezing by construction rather than auditing after the fact, because a practitioner cannot know in advance which clauses those will be.
ON THE PRICE OF FREEZING. POLICY-1 puts ≈26 pp of proxy metric on the table, which makes this the adversarial case for Proposition 2 rather than the typical one: we froze the single clause the optimizer most wanted to remove. The measured price of doing so is 10.5 pp. The bound itself is not testable here: its right-hand side combines γ \gamma γ , which we cannot estimate per benchmark, with a maximum over the counterfactual variant sets V i \mathcal{V}_i V i , which are unobservable by construction (Remark 15). This arm instead tests the proposition’s shape (that the price tracks the marginal value of what was frozen) at both ends of that range. The claim of Section E.6, that freezing is nearly free when frozen blocks carry small marginal gains, concerns metric-neutral contracts, and the tool schema, safety text and output envelope, untouched by every arm in every candidate, are the evidence for it at zero cost. POLICY-1 is the deliberate stress case at the other end, and 10.5 pp against 26 pp of forgone proxy metric is the number a practitioner should budget for when a frozen clause is expensive.
LIMITS. Three seeds, one task, one target model, and the arms consumed different budgets (456 candidates for A1 against 336, 372 and 408 for A2–A4), which if anything favors A1, so the editable arms’ lead on the proxy is not a budget effect. Text preservation is not behavioral compliance, and the gap between them is the sharpest scope condition the experiment produces. With the clause present and no optimization (the seed, A0), the target complies on 96.5% of triggered test examples; in A1 the clause is byte-identical and compliance is 66.8%. The only difference between those two conditions is the optimizer’s edits to the mutable blocks, which share a token stream with the frozen one and were optimized under a metric that pays for violation. So the most natural reading is that optimized neighbors partly override a frozen clause: freezing protects a block’s text, not its effect. Baseline non-compliance does not explain the drop, since A0 is that baseline on the same test split; what the experiment does not identify is which edits to the neighboring blocks erode the clause. The editable arms’ 0–1.4% has a different cause in each arm. A2 deleted the clause in most candidates, so there compliance was never possible; A3 and A4 kept it present (A4 retained it verbatim in 111 of 408 candidates and deleted it in none) and complied anyway at ≤ 1.4 % \le1.4\% ≤ 1.4% , so a clause that survives in place but is paraphrased, or surrounded by optimized text, can lose its force entirely. Finally, the mechanism is aimed at silent failures; a contract whose violations raise a parser or schema error is caught by output validation and does not need it.
Knobs, and Where They Fail
The two axes here are ones a practitioner has to set, and neither of them behaves like a monotone quality dial. Search budget is non-monotonic in N N N , and trading beam width for per-parent fan-out at a fixed budget did not move the leader; momentum has no measurable effect at its default and a measurable cost at a longer window.
Search Budget: Proposer Draws and Beam Width
We characterize the weakest iterative regime first: Best-of-N N N sampling with no feedback.
Figure 3 reports BoN accuracy across proposer scales and N ∈ { 1 , 3 , 5 , 10 , 15 } N \in\{1, 3, 5, 10, 15\} N ∈ { 1 , 3 , 5 , 10 , 15 } on SST-5 and GPQA-Diamond, from a separate run that varies the proposer. One-shot accuracy scales strongly with proposer capacity: on SST-5 the fitted accuracy rises from ∼ 45 % \sim45\% ∼ 45% for the smallest proposers to ∼ 55 % \sim55\% ∼ 55% for the largest. But within that run the five N N N -curves lie within a narrow band at every proposer Turning momentum off costs +0.44 pp paired with the sign consistent on all three seeds, but that is about six times smaller than the 2.5 pp cross-seed standard deviation, and on a 300-example split 0.33 pp is a single example, so the supported statement is no measurable effect , not no effect . The w = 10 w=10 w = 10 arm is different: it loses 2.44 pp paired, consistently on every seed, and terminates at 5.3 steps against the control’s 12.7, less than half the search. Its proposal win rate is the highest of any arm, which is coherent rather than noisy: a long critique history over-constrains the proposer, so the edits it does produce beat their parent more often but explore a narrower region, and the run early-stops at a worse leader. Momentum’s window is a real knob with a wrong end: w = 5 w=5 w = 5 is a reasonable choice, extending it is not.
size, so drawing more samples from the same seed without feedback does not substitute for a larger proposer. The GPQA target sweep shows the same lack of a reliable N N N -trend with the proposer fixed: aggregate accuracy peaks at N = 10 N=10 N = 10 and drops at N = 15 N=15 N = 15 , as does the small target tier, the large tier peaks at N = 5 N=5 N = 5 , and the frontier tier rises from N = 10 N=10 N = 10 to N = 15 N=15 N = 15 (Figure 16 in Section F; its cells carry roughly ± 20 \pm20 ± 20 pp of sampling uncertainty on a difference). The companion axis is beam width W W W . At a fixed per-step variant budget W k = 12 Wk = 12 W k = 12 , trading width for per-parent depth (W = 4 W=4 W = 4 , k = 3 k=3 k = 3 against W = 2 W=2 W = 2 , k = 6 k=6 k = 6 ) did not move the leader’s mean. These are single runs per configuration, so we make no claim about the effect on run-to-run variance, and the comparison does not bear on Theorem 2, which concerns the re-evaluation regime SPLICE does not use. It does not test Conjecture 1 either, which varies W W W at fixed k k k ; that conjecture currently has no empirical handle in this paper. The beam widths used per benchmark (W = 4 W=4 W = 4 or 5 5 5 , Section F.1) are not tuned defaults.
Momentum
Momentum is part of the critique axis of § 2 , and its ablation returns a null. Table 13 isolates it on SST-5 across four arms (off, and window w ∈ { 2 , 5 , 10 } w \in\{2,5,10\} w ∈ { 2 , 5 , 10 } ) with three seeds paired across arms and each arm differing from the control in exactly one field.
Two findings, pointing in different directions. Turning momentum off costs nothing measurable. The paired mean is +0.44 pp in the control’s favor and the sign is consistent on all three seeds, so we do not claim momentum helps at the default window. But the magnitude is about six times smaller than the 2.5 pp cross-seed standard deviation, and on a 300-example validation split 0.33 pp is a single example, which two of the three per-seed gaps are. Windows 2 and 5 are likewise indistinguishable. The supported statement is no measurable effect , not no effect : three seeds on this benchmark cannot resolve an effect this small. A long window is measurably worse. At w = 10 w=10 w = 10 the arm loses 2.44 pp paired, consistently on every seed, and terminates at 5.3 steps against the control’s 12.7 (less than half the search) while recording the highest proposal win rate of any arm (0.308). That combination is consistent with a long critique history over-constraining the proposer, so that the edits it does produce beat their parent more often but explore a narrower region, and the run early-stops at a worse leader; we do not measure the explored region directly. Momentum’s window is a real knob with a wrong end.
The cross-benchmark evidence agrees. On HelpSteer2, eight matched pairs drawn from a 114-run sweep gave a mean effect of +0.009 Spearman ρ \rho ρ with momentum winning three and losing five; on ARC, eight matched pairs give −0.001, nominally hurting six of eight. Across three benchmarks, two metrics and 19 matched pairs there is no effect outside noise on any of them. Two observations belong with that null rather than against it: ARC is saturated (in this sweep the median initial prompt
scores 0.963, median run improving 0.004), so it cannot resolve small effects, and the ARC and HelpSteer2 sweeps lack replicates, so a true effect below the noise floor would be invisible.
The implementation tags each momentum entry HELPED, HURT or FLAT by the leader’s gain Δ s \Delta_s Δ s relative to Δ min \Delta_{\min} Δ m i n , and warns when three consecutive significant gains alternate in sign. Under elitist selection with cached scores the leader never falls (Lemma 1), so Δ s ≥ 0 \Delta_s \ge0 Δ s ≥ 0 : only HELPED and FLAT can occur, and the oscillation warning cannot fire. The absence of oscillation is therefore a property of the selector, not an observation, and momentum acts as a record of which directions moved the leader. Its benefit is undemonstrated rather than refuted, and w = 5 w=5 w = 5 should be read as a reasonable default rather than a tuned one.
When Iteration Pays: Capacity, p-star, and Cost
The three measurements in this subsection are one argument. Iterative search buys its advantage from the rate at which the (proposer, target) pair generates improving edits; that rate is directly measured; and whether the advantage is worth paying for depends on what the search costs. Taken together they answer the question a practitioner actually asks before adopting the method: on my task and my model, should I iterate, or sample once and take the best? They answer it with a diagnostic that can be run in the first few steps rather than with a benchmark table.
The GPQA-Diamond sweep (set up in § 4 ) varies the target across six models in three tiers while holding the proposer fixed. Averaged over targets, Elitist Beam (64.6%), BoN N = 10 N=10 N = 10 (63.3%) and Beam (62.9%) are within noise of one another: one question is 2.5 pp, a difference between two single cells carries about ±20 pp of sampling uncertainty, and a difference between two six-fold averages about ±9 pp. The per-tier view (Figure 15 in Section F) is where a pattern shows: iterative strategies score highest on the frontier tier, and no strategy consistently wins on the small tier, where Section F.4.1 measures p ^ ⋆ = 0.21 \hat{p}^{\star}=0.21 p ^ ⋆ = 0.21 , so 1 − ( 1 − p ^ ⋆ ) k ≈ 0.51 1-(1-\hat{p}^{\star})^{k}\approx0.51 1 − ( 1 − p ^ ⋆ ) k ≈ 0.51 at k = 3 k=3 k = 3 . Section F.7 gives the BoN-scaling, train–validation and cost views of the same sweep.
The Improving-Proposal Rate p-star
THE MEDIATING QUANTITY, MEASURED. Table 14 reports p ^ ⋆ \hat{p}^{\star} p ^ ⋆ , the per-step fraction of proposed children whose validation score exceeds their parent’s. This is the success event of Assumption 1, averaged over the parents the search visited, so it estimates the improving-proposal probability of that assumption on average rather than in the worst case. It is the single most informative diagnostic in the paper, because it reads in two directions at once and each direction discharges a different claim.
Table 14. The improving-proposal rate p ^ ⋆ \hat{p}^{\star} p ^ ⋆ , measured, at W k = 12 Wk=12 W k = 12 . Every run logs the per-step fraction of proposed children whose validation score exceeds their parent’s; this table is extracted from existing logs, with two folds per GPQA tier. On GPQA the proposer is fixed and the columns are target tiers. Down the column , coverage is abundant while the prompt still has deficiencies the critique can name, then decays by an order of magnitude as the leader climbs, the state-dependence that the ϵ \epsilon ϵ -sublevel form of Assumption 1 allows. Across the row , p ^ ⋆ \hat{p}^{\star} p ^ ⋆ increases with target capacity. The last row substitutes the tier mean into the leader-advance rate of Theorem 4, 1 − ( 1 − p ^ ⋆ ) k 1-(1-\hat{p}^{\star})^{k} 1 − ( 1 − p ^ ⋆ ) k , as a proxy: the theorem’s rate uses only the leader’s own k k k draws, and p ~ \tilde{p} p ~ counts only gains of at least Δ min \Delta_{\min} Δ m i n . It orders the tiers the way iteration’s advantage over Best-of-N N N does; the per-step rate 1 − ( 1 − p ^ ⋆ ) W k 1-(1-\hat{p}^{\star})^{Wk} 1 − ( 1 − p ^ ⋆ ) W k is at least 0.94 on every tier and does not. The rate averages over the states the search visited, so it upper-bounds the worst-case quantity in Assumption 1. One improving child out of twelve is already p ^ ⋆ = 0.08 \hat{p}^{\star}=0.08 p ^ ⋆ = 0.08 , so we read only sustained zeros as a plateau. Single seed (random_seed=42), one run per (fold, strategy).
Down the column it traces state-dependence. Coverage is abundant while the prompt still has deficiencies the critique can name (0.92 at step 2 on SST-5, 0.58–0.83 on frontier GPQA folds), then decays by an order of magnitude as the leader climbs, reaching zero in several late steps. This is an empirical trace of p ^ ⋆ ( ε ) \hat{p}^{\star}(\varepsilon) p ^ ⋆ ( ε ) as ε \varepsilon ε shrinks, and it is what the ε \varepsilon ε -sublevel form of Assumption 1 predicts rather than something in tension with it. The terminal zeros are the stopping condition being met, not the assumption failing: they occur after the leader has plateaued, at states whose remaining gap is below what the search can resolve, which is why SPLICE exits on consecutive no-improvement steps rather than spending the remaining budget.
Across the row it gives a measured mechanism for the target-capacity effect of § 4 . With the proposer fixed, tier means at step 2 are 0.71 (frontier), 0.50 (large) and 0.21 (small): p ^ ⋆ \hat{p}^{\star} p ^ ⋆ increases with target capacity, so the improving-proposal rate is a property of the (proposer, target, task) triple, not of the proposer alone. Which rate to read it through matters. Substituting p ^ ⋆ \hat{p}^{\star} p ^ ⋆ into the per-step reachability rate gives 1 − ( 1 − p ^ ⋆ ) W k ≥ 0.94 1-(1-\hat{p}^{\star})^{W_k}\ge0.94 1 − ( 1 − p ^ ⋆ ) W k ≥ 0.94 for all three tiers at W k = 12 W_k=12 W k = 12 , which predicts that iteration should pay everywhere, and it does not on small targets. Substituting it into the leader-advance rate of Theorem 4 gives 1 − ( 1 − p ^ ⋆ ) k = 0.98 1-(1-\hat{p}^{\star})^k=0.98 1 − ( 1 − p ^ ⋆ ) k = 0.98 , 0.88 and 0.51 at k = 3 k=3 k = 3 , an ordering that matches where iteration separates from one-shot sampling. The second substitution is a proxy: the theorem’s rate p a d v p^{\mathrm{adv}} p adv uses only the leader’s own k k k draws, and p ~ ⋆ \tilde{p}^{\star} p ~ ⋆ (Assumption 5) counts only gains of at least Δ min \Delta_{\min} Δ m i n , while p ^ ⋆ \hat{p}^{\star} p ^ ⋆ counts every parent’s children and any positive gain. We did not compute the leader-only, thresholded rate, so these values indicate the advance rate rather than measure the theorem’s quantity. The convergence-relevant floor is therefore 1 / k ≈ 0.33 1/k\approx0.33 1/ k ≈ 0.33 , not the per-step resolution floor 1 / W k ≈ 0.08 1/W_k\approx0.08 1/ W k ≈ 0.08 , and the small-tier mean sits below it; small-tier runs also stop early, after about six steps.
Two consequences we would rather state than leave implicit. First, this makes the scope condition of § 4 operational: SPLICE’s iterative advantage needs a p ^ ⋆ \hat{p}^{\star} p ^ ⋆ well above 1 / k 1/k 1/ k , and below that one-shot sampling is a reasonable choice when the task is saturated, though not always, since on the judge task (Section F.5) Best-of-N N N regresses below its seed. Second, because the rate is observable within the first few steps of any run, it doubles as a cheap pre-flight check on a practitioner’s own (task, proposer, target) triple. The caveats are in Table 14 : these are single-seed runs, one per (fold, strategy); the observed rate averages over the states the search visited, so it upper-bounds the worst-case p ⋆ ( ε ) p^{\star}(\varepsilon) p ⋆ ( ε ) of Assumption 1 rather than estimating it; and it cannot distinguish convergence to ε \varepsilon ε -optimality from a radius-one local maximum, since both appear as zeros.
Cost
Cost splits into two questions that are easy to conflate, and only one of them admits a fair comparison against prior work.
INFERENCE-TIME COST OF THE RETURNED PROMPT. This is measured and comparable, since every method is evaluated on the same BBH test set through the same task model. Table 15 reports it: SPLICE’s optimized prompt costs 1,452 total tokens per example against GEPA’s 1,727 (the SPLICE mean is over the 181 of 405 test calls that survive in the response cache), 16% fewer tokens per example (a 1.19× \times × ratio), driven almost entirely by 2.9× \times × fewer completion tokens (128 against 373) at near-identical prompt length (1,325 against 1,354). The claim we make is therefore comparable prompt size, substantially shorter outputs rather than a large total-cost win, and two caveats travel with it: the completion figure is low enough relative to every other method that it may in part reflect suppressed intermediate reasoning, and the harness evaluates SPLICE through a raw completion call while the other rows pass through a chain-of-thought wrapper, an asymmetry that inflates their completion counts.
Table 15. Inference-time cost of the returned prompt. BBH, 405 test examples, identical task model (claude-haiku-4-5) for every row. Each column is a rounded per-example mean, so a total can differ from the sum of its parts by one. SPLICE’s optimized prompt costs 1.19× less per example than GEPA’s, and the gain is almost entirely on the output side: 2.9× fewer completion tokens at near-identical prompt length (1,325 against 1,354). The supported claim is therefore comparable prompt size, substantially shorter outputs , not a large total-cost win. We report per-example figures only and omit totals, because only 181 of 405 SPLICE calls survive in the response cache, so its totals are not full-test-set totals and would not be comparable with the other rows’. Two caveats travel with the completion-token figure: it is low enough relative to every other method that it could in part reflect suppressed intermediate reasoning rather than pure efficiency, and the harness evaluates SPLICE through a raw completion call while the other rows pass through a chain-of-thought wrapper, an asymmetry that inflates their completion counts. Optimization-time cost is deliberately not compared here; see ‘What we do not report’ below.
OPTIMIZATION-TIME COST WITHIN SPLICE. Across selectors on GPQA, where the instrumentation is identical for every row, Elitist Beam reaches the highest validation accuracy on 24% fewer tracked tokens than Beam (1.06M against 1.39M per fold, excluding candidate scoring; Table 16 in Section F), a 26% better cost-per-accuracy ratio. On BBH the diversity arms reach their best score at step 4 while div0 never passes 0.213 in 13 steps (Table 12 ), so the diversity arms also reach their best much earlier; we do not have per-arm token counts for that sweep and so give no ratio.
Table 16 : GPQA validation accuracy by search strategy (Elitist Beam here uses D = 0 D=0 D = 0 , so it differs from Beam only in keeping parents), mean ± \pm ± s.d. across the six target models, not across seeds. Every run is random_seed=42, one run per (model, strategy), so the large spreads are substantially the tier effect of Figure 15 rather than run-to-run variance; no seed replicates exist for this sweep. Train–val gap is a diagnostic, not an objective: iterative training scores are averaged over the steps’ training batches, while a BoN run logs a single batch; every arm selects on D v a l i d D_{\mathrm{valid}} D valid . Gap is computed from unrounded means and can differ from the rounded columns by 0.1. The sweep has no test split, so the gap says nothing about validation optimism.
Table 16.
On GPQA, Elitist Beam costs 12–41× \times × a Best-of-N N N run per fold depending on N N N (Table 16 ), and BoN(N N N =10) lands 1.3 pp below it at roughly 6% of the token cost, a difference this sample cannot resolve. So our conclusion is elitist-versus-beam, not iterative-versus-one-shot: where budget binds on a saturated task, one-shot sampling is a reasonable choice (though not on the judge task, where it regresses below the seed), and the p ^ ⋆ \hat{p}^{\star} p ^ ⋆ diagnostic of Section F.4.1 is the cheap way to decide which regime a given (task, proposer, target) triple is in.
WHAT WE DO NOT REPORT, AND WHY. There is no SPLICE-versus-GEPA comparison on optimization-time cost. Our own instrumentation does not populate the candidate-scoring bucket, which is the dominant term (each scored candidate consumes a full evaluation batch, so the tracked figures understate true optimization cost by roughly 40×), and the GEPA reproduction logged no optimizer tokens at all, its reflection and mutation calls never having been cached. Publishing a partially instrumented number of ours against an absent number of theirs, in our own favor, is precisely the asymmetry a cost table should not contain. Closing this requires instrumenting both sides and re-running under a matched optimizer budget, which we scope as future work rather than estimate here.
Application: LLM-as-Judge Rubric Calibration
The benchmarks above all optimize prompts whose output is the system’s primary task response. Here we apply SPLICE to a task of a different kind: optimizing the rubric prompt given to an LLM-as-judge so that its ratings align with human annotations. The framework is unchanged (the rubric text is the block-structured state, the judge’s output is an intermediate signal, and the scalar metric is the rank correlation of that output with ground truth), but the target has shifted from “get the task right” to “predict human preferences correctly.” Judge rubrics are a natural application regime for the method: they are long, multi-section artifacts whose failure modes are mis-calibrations rather than outright errors, and they are increasingly used as the scoring mechanism for other prompt-optimization pipelines.
Task and data. We use the NVIDIA HelpSteer2 dataset [80 ] , which provides human ratings for assistant responses across five criteria on a 1–5 scale: helpfulness/understanding, correctness/completeness, coherence/clarity, language complexity, and succinctness/verbosity. The judge receives a rubric prompt containing an overall-quality rubric and a per-level description for each of the five criteria; given a (user prompt, assistant response) pair, it emits six scalar scores. The metric is the mean Spearman rank correlation between the judge’s scores and the human ratings, averaged across the five criteria. Scoring uses a stratified 400-example validation split; each step’s training batch has 64 examples. Proposal temperature is 0.9 and critique temperature 0.0.
Judge models. We evaluate across the six judge models S1–F2 of § 4 , two per tier (Small, Large, Frontier). The initial hand-crafted rubric reaches mean Spearman ρ = 0.555 \rho= 0.555 ρ = 0.555 across these six models, a competitive baseline that sets a high bar for any automated optimizer.
Results. Figure 10 reports mean validation Spearman ρ \rho ρ across the six judge models. The best iterative strategy (Elitist Beam, D = 2 D=2 D = 2 , parent mode) reaches ρ = 0.674 \rho= 0.674 ρ = 0.674 , followed by Beam at 0.673 and Greedy at 0.610. The best single-run configuration is F1 with Elitist Beam, at ρ = 0.736 \rho= 0.736 ρ = 0.736 . None of the Best-of-N N N configurations match the iterative results: the best BoN mean is 0.546 (N N N =5), more than 0.12 below the Elitist Beam mean, and BoN mean-over-N N N is non-monotonic (N N N =1:0.476, 3:0.506, 5:0.546, 10:0.484, 15:0.518). The gap between iterative search and single-step sampling is wider on this task than on any of the public benchmarks in the main text.
Figure 10. Judge Alignment on HelpSteer2: iterative search vs. single-step sampling. Mean validation Spearman ρ \rho ρ between the optimized judge and human annotations across six judge models (error bars: standard deviation across models). The initial hand-crafted rubric (red dashed line, ρ = 0.555 \rho=0.555 ρ = 0.555 ) is a competitive baseline that none of the Best-of-N N N configurations matches on average. All three iterative strategies improve over the seed; Best-of-N N N regresses below it.
Single-step sampling regresses below the seed. On this dataset Best-of-N N N sampling actively degrades the prompt relative to the hand-crafted seed. The mean improvement over the seed is −0.049 averaged across all five BoN configurations, so on average BoN leaves the prompt worse than the seed. Iterative strategies move in the opposite direction, improving over the seed by +0.097 on average. Variance decomposes the effect further: across judge models, the standard deviation of BoN scores is 0.166, compared to 0.063 for iterative strategies. On this task BoN is not merely weaker in expectation; for individual judge models it is sometimes catastrophic (e.g. ρ \rho ρ = 0.18 on L2 with BoN N N N =1, compared to 0.614 for Elitist Beam on the same model). The iterative-vs-BoN gap is therefore not a question of whether more samples would eventually match search: on a task where the prompt is sensitive to small-scale calibration choices, up to N N N =15, proposer-only sampling does not recover what iterative critique + selection delivers.
The elitist property prevents leader regression. Elitist Beam (0.674) and Beam (0.673) achieve nearly identical means, but the mechanism differs in a way that matters for worst-case behavior. Under Beam, the final leader may be worse than the best candidate seen during optimization; under Elitist Beam with the cached-scoring convention of § 2 , the leader score is monotone non-decreasing (Lemma 1). Greedy (ρ \rho ρ = 0.610) suffers most from regression: on S2 its final leader drops to 0.402 even though a stronger candidate appeared earlier in the search. Across the six judge models, greedy’s standard deviation is 0.110, approaching BoN-level variance despite iterative search, a direct consequence of maintaining only a single candidate with no fallback when it regresses. Beam and Elitist Beam standard deviations across the six judge models are 0.033 and 0.046 respectively, against 0.166 for BoN.
What SPLICE discovered. Inspecting the optimized rubric reveals four calibration strategies that the seed lacks, each aimed at a way the seed rubric can mis-calibrate the judge. (i ) Descriptive vs. evaluative dimension separation. Language complexity and verbosity are descriptive (a simple response is not worse than a complex one), whereas helpfulness, correctness, and coherence are evaluative. The optimized rubric marks the first two as “descriptive only” and instructs the judge that low scores on these dimensions must not reduce the overall score, a distinction absent from the symmetric seed. (ii ) Anti-defamation gates. The optimized prompt contains explicit “default high” clauses and mandatory upgrade-before-downgrade tests (“before assigning score 3, ask: can I name ONE specific factual claim that is clearly wrong AND central to the answer? If not, you MUST score 4”) that guard against systematic under-scoring. (iii) Structured scoring decision trees. Rather than the seed’s per-level prose, the optimized rubric encodes a four-step decision procedure (topic relevance → task understanding → substantive correctness → named-flaw test), where each step maps to a minimum score. (iv) Dual-track overall scoring. Two independent tracks (core-quality threshold on helpfulness, correctness, and coherence; or arithmetic mean above a cutoff) each suffice for the top overall score, preventing descriptive dimensions from dragging down the aggregate. These mechanisms are specific and interpretable, and SPLICE discovers them from rank-correlation feedback alone, without any auxiliary supervision on where the judge is mis-calibrated.
Figure 11. Only the elitist D = 1 D=1 D = 1 variants beat critique-guided one-shot sampling. Bars report test accuracy of the final leader, mean over three runs, for every iterative strategy (red: Greedy, Beam, Elitist Beam) and every one-shot baseline (yellow: BoN with critique; grey: plain BoN). Dashed lines mark published numbers for prior optimizers from [89 ] (left) and [94 ] (right). The elitist variants lead the best BoN+critique arm by 3.0 pp (Gemma) and 1.8 pp (DeepSeek); Greedy and Beam fall below it.
The remaining subsections give supporting diagnostics: the SST-5 strategy sweep against published numbers (Section F.6), GPQA-Diamond search trees and per-tier, BoN-scaling, train–validation and cost views (Section F.7), and SST-5 lineage and score traces (Section F.8).
Additional Search Strategy Ablations
Figure 11 places every SPLICE variant shown (Elitist Beam with D = 1 D=1 D = 1 , parent and lineage modes), the Greedy and Beam arms, and every Best-of-N N N baseline on the same axes as the published prior-method numbers, for the two SST-5 target models. Three points follow. First, the top two positions on both target models are occupied by SPLICE variants with D = 1 D=1 D = 1 diversity (parent and lineage modes). The figure has no D = 0 D=0 D = 0 elitist arm, so it shows that the D = 1 D=1 D = 1 variants rank highest, not that the slot is the reason. Second, the best elitist variant leads the best BoN+critique configuration by 3.0 pp on Gemma and 1.8 pp on DeepSeek, while Greedy and Beam fall below it, so on SST-5 the margin over one-shot sampling comes from elitist search, not from iteration alone. Third, critique changes plain BoN by − 1.6 -1.6 − 1.6 to + 2.8 +2.8 + 2.8 pp (positive in nine of ten pairs; compare Figure 4 a). Figure 12 gives the ARC-Challenge counterpart of Figure 4 b.
GPQA-Diamond: Search-Tree Topology
Figure 13 expands the search-tree footprint discussion of § 4 : the search-tree grid visualizes the exploration footprint of each selector on frontier target models. This figure, Figure 20 and the case studies of Section F.7.5 come from a separate GPQA run with the same strategies and targets as the sweep of Section 4, so their final scores need not match Figure 15. In the panel titles of the GPQA figures, Claude Sonnet 4 and Claude Opus 4 abbreviate the F1 and F2 targets claude-sonnet-4-6 and claude-opus-4-6, and the other names denote S1–L2 in the order of § 4 .
Greedy produces ∼ \sim ∼ 19-node chains, Beam produces 61–97-node trees, and Elitist Beam sits between at ∼ \sim ∼ 40 nodes.
The main text (§ 4 ) summarizes this sweep; Table 16 gives its aggregate, and this subsection holds the remaining views of the same runs: per-tier bars, Best-of-N N N scaling, the train–validation gap, the cost–accuracy Pareto, search-tree topology across all six models, and three qualitative case studies. For reference, the sweep is eight strategies (Greedy, Beam, Elitist Beam, and Best-of-N N N at
N ∈ { 1 , 3 , 5 , 10 , 15 } N \in\{1, 3, 5, 10, 15\} N ∈ { 1 , 3 , 5 , 10 , 15 } across six target models (S1–F2, § 4 ). All runs use one fixed proposal agent (temperature 0.9) and one fixed critique agent (temperature 0.0); the validation split has 40 questions, scored by exact match. Iterative strategies use 3 proposals per candidate, early-stopping patience of 5, and up to 50 steps.
Figure 15 isolates each tier. On frontier models, Beam (87.5%) and Elitist Beam (83.8%) score highest, with BoN N N N =3 close behind (81.3%). On large models, Elitist Beam is the single best strategy (65.0%), with BoN N N N =5 and N N N =10 near 60%. On small models the bars span 39–59% with overlapping error bars and BoN N N N =10 is highest: strategy choice matters less than model capability at this scale.
Best-of-N N N Scaling Is Non-Monotonic
Figure 16 tracks how BoN accuracy changes as N N N increases. Scaling is non-monotonic : the overall and small-tier curves peak at N N N =10 and drop at N N N =15, the large tier peaks at N N N =5, and the frontier tier peaks at N N N =3 and rises again from N N N =10 to N N N =15. Small models gain most from larger N N N (38.8% to 58.8%). Each cell is a single independent run, so these differences are within run-to-run sampling noise and should not be read as a trend in N N N .
Train–Validation Gap by Strategy
Figure 17 shows the gap between training and validation accuracy, strategy by strategy. Iterative strategies hover near zero: their training scores, averaged over many batches, track validation. BoN strategies show large negative gaps (validation ≫ \gg ≫ train): one training batch is a noisy score, and the validation score of the selected candidate is biased upward by selection. Because every arm selects on D v a l i d \mathcal{D}_{\mathrm{valid}} D valid , the gap does not change which prompt BoN returns.
Figure 18 shows the same from a different angle. Iterative runs (circles) cluster along the diagonal and BoN runs (squares) sit far above it, across all model tiers. The difference is one of measurement: an iterative run’s training score is averaged over many steps’ batches, while a BoN run logs a single batch, so the gap reflects how training accuracy is recorded rather than a difference in how well either strategy generalizes.
Figure 18. Train vs. validation accuracy on GPQA-Diamond. Iterative strategies track the diagonal; BoN strategies overshoot.
Cost–Performance Trade-off
Table 16 gives accuracy and token cost per strategy, averaged over the six targets, and Figure 19 plots token cost against validation accuracy for every (model, strategy) run. The runs split by cost rather than accuracy: BoN runs use about 18–90K tokens and iterative runs 250K–2.7M, while both span roughly 30–88% accuracy, ordered mainly by target model. For budget-constrained settings, BoN N = 10 N=10 N = 10 at 67K tokens offers 63.3% accuracy, competitive with iterative methods that cost 5–21× more; this is the one regime in which one-shot sampling is a reasonable default, and it relies on a validation split large enough to control selection noise, which the 40-question GPQA split is not.
Figure 19. Cost vs. accuracy on GPQA-Diamond. Circles = iterative, squares = BoN; colors = target model.
Elitist Beam Search Trees Across All Six Models
Figure 13 shows the search-tree footprint across strategies on frontier targets; the complementary view in Figure 20 fixes the strategy at Elitist Beam and sweeps the target model across all six target models (three tiers). Frontier models converge in ∼ 40 \sim40 ∼ 40 nodes, matching the frontier column of Figure 13 , while large models need up to 136 nodes, 3.4 × 3.4\times 3.4 × more exploration to find a good prompt. This mirrors the per-tier accuracy results: harder optimization landscapes require more search, and the elitist selector supplies it without sacrificing the monotonicity guarantee of Lemma 1.
Figure 20. Elitist Beam search trees across all six target models on GPQA-Diamond. Frontier models (bottom middle and right) converge in ∼ 40 \sim40 ∼ 40 nodes, small models (top left and middle) take 64, and large models (top right, bottom left) need up to 136. Node color encodes validation score (red = low, green = high); the red path traces the lineage of the best candidate.
Case Studies: What Iterative Refinement Discovers
Three representative F1 runs illustrate how a prompt is refined along the best-scoring lineage.
Elitist Beam (62% → \to → 85%). The seed prompt (c 0 c_0 c 0 ) contains only a bare objective: “Answer the following multiple choice question by reasoning through it step by step.” In generation 1, the optimizer adds a <role> (“expert scientist and problem solver”), a structured <approach> with numbered steps, and a few-shot example, but the score rises only to 68% (c 2 c_2 c 2 ). The breakthrough comes in generation 2 (c 4 c_4 c 4 , 85%): the approach is rewritten to enforce plain prose reasoning (“no markdown headers, no numbered sub-sections, no bullet lists”) and a 2–5 sentence budget, plus the objective is tightened to require sufficient justification. This formatting constraint prevents the model from wasting tokens on verbose structure and forces it to reason concisely, a lesson the optimizer discovered from critique feedback on failed examples.
Greedy (57% → \to → 78%). The Greedy run shows a different refinement trajectory across four nodes. Generation 1 (c 1 c_1 c 1 , 72%) introduces a decisive persona (“prioritize reaching a clear, correct final answer over exhaustive explanation”) and a concise approach. Generation 2 (c 4 c_4 c 4 , 75%) adds a strict word budget (“if your reasoning would exceed 8 sentences, stop and state your best answer”) and option-scanning heuristics. Generation 3 (c 9 c_9 c 9 , 78%) bans all markdown formatting and imposes a hard 150-word reasoning cap. Each refinement targets a specific failure mode: verbose responses that get truncated before stating an answer, markdown that confuses answer extraction, and over-analysis that leads to second-guessing.
Beam W = 4 W=4 W = 4 (52% → 85%). The Beam run traverses seven nodes (c 0 → c 2 → c 9 → c 22 → c 33 → c 42 → c 53 c_0 \to c_2 \to c_9 \to c_{22} \to c_{33} \to c_{42} \to c_{53} c 0 → c 2 → c 9 → c 22 → c 33 → c 42 → c 53 ), the longest best-path lineage among our runs. Generation 1 (c 2 c_2 c 2 , 65%) adds a SCAN/FOCUS/REASON structure and a “no backtracking” directive. The critical insight arrives at generation 3 (c 22 c_{22} c 22 , 68%): the objective is rewritten to declare that “reasoning without a final answer is a failure regardless of quality,” and the approach shifts to answer-first-then-verify. Generation 4 (c 33 c_{33} c 33 , 70%) escalates further: “state your best answer BEFORE verification.” Generation 5 (c 42 c_{42} c 42 , 78%) introduces explicit word budgets and simplifies the approach to three steps. The final node (c 53 c_{53} c 53 , generation 6, 85%) imposes a hard 250-word cap and adds a fourth example. The trajectory reveals a consistent theme: each generation tightens the contract between reasoning depth and answer reliability, progressively learning that completing the answer matters more than showing all work.
Recurring refinement themes. Across all three runs three patterns emerge. (i) Format discipline: early steps add formatting constraints (plain text, no markdown, word limits) that prevent answer-extraction failures. (ii) Reasoning calibration: later steps tune the depth of reasoning, encouraging quick elimination for conceptual questions and systematic derivation for multi-step problems. (iii) Few-shot accumulation: examples are added incrementally (1 → 2 → 3 → 4 across generations), each targeting a different question archetype (recall, calculation, synthesis, spectral analysis). None of these themes are present in the seed; all are discovered from scalar validation feedback and textual gradients alone.
Candidate Lineage and Score Progression on SST-5
Figure 13 in Section F.7 shows the search-tree footprint on GPQA-Diamond. The analogous view for SST-5 is reported here.
Figure 21 traces the best-leader validation accuracy along the search step index, and Figure 22 shows the candidate-lineage graph on the best SST-5 run. Two patterns appear. (i) Monotone best-path score. The leader accuracy is non-decreasing along the best-scoring lineage, the empirical signature of Lemma 1 under the cached-scoring convention. (ii) Early but not only early gains. About two-thirds of the 5.2 pp gain arrives by generation 4, and the last +1.4 pp at about generation 9. This matches the improving-proposal rate being highest early in the search (Section F.4.1).
Figure 21. SST-5: the carried leader never falls, and most of its gain comes early. One run. Dots are candidates by ID, colored by generation; the red line is the beam leader, which rises from 54.0% to 59.2%, about two-thirds of the gain by generation 4.
Figure 22. SST-5: the search fans out early, then concentrates on one branch. Candidate lineage graph for one run. Nodes are candidate prompts colored by validation accuracy (red = low, green = high); edges connect a candidate to the parent(s) it was proposed from. The ringed node is the final best candidate. The fan-out pattern at early generations reflects the Elitist Beam selector filling its diversity slots (Theorem 6 ) before converging on the best-scoring branch.
Beam diversity and proposer success rate. Two further per-step diagnostics on SST-5 track how the selector and proposer behave inside the search loop. Figure 23 reports the best validation score and the spread of beam scores at each generation. After step 1 the spread stays small, so the beam’s members score alike while the leader climbs.
Figure 23. SST-5: after the first step, beam members score alike. Best validation score (line) and the spread of beam members’ scores (bars) at each generation of the Elitist Beam run.
Figure 24 reports the complementary quantity on the proposer side: the fraction of candidate children whose validation score exceeds their parent’s, measured per search step. Under the deterministic monotonicity of Lemma 1 the leader is non-decreasing by construction, but the per-proposal success rate is an empirical quantity: it says how often a textual-gradient-conditioned proposal actually improves on its parent. That fraction is itself a per-proposal rate (it is p ^ \hat{p} p ^ , a direct estimate of the per-proposal rate, not the per-step reachability probability), and on SST-5 it is 11/12 at step 2, at most 3/12 from step 3, and zero in most steps after step 6, falling as the leader climbs. This run is not the one tabulated in Table 14 , whose SST-5 column falls to 0.08–0.17 by steps 4–5; the two should be read as different runs, not as one rate.
Figure 24. SST-5: improving proposals are common early and rare later. Fraction of proposed children whose validation score exceeds their parent’s, per step: 11/12 at step 2, at most 3/12 from step 3, and zero in most steps after step 6.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction claim an edit-graph formalization, selective mutability with a price-of-freezing bound, an elitist selector with diversity slots and its guarantees, reachability and convergence results under a stated proposer condition, a length-regularization bias bound, and empirical results: wins on four of seven public benchmarks and matches on three (a margin of at most 0.5 pp), plus a contract stress test. These are substantiated in Sections 2 to 4 and, in full, Sections E to F.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 5 states the main limitations: the guarantees are conditional on proposal coverage and on a submodularity ratio for which there is no estimator; freezing preserves a contract’s text but not its effect (compliance falls from 96.5% to 66.8% in Section 4); a misspecified reward is the dominant failure mode. Section E states what is and is not provable, and Section F reports null and negative ablation results (e.g. momentum).
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Every theorem-like statement is given with its assumptions in Section 3 or Section E, and complete proofs are in Section E. Results that are not proved are labelled as conjectures.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 4 specifies all benchmarks, target models and the published protocols reproduced without modification; Algorithm 1 gives the full procedure; Section F gives protocols, splits and hyperparameters, and Section A gives optimized prompts.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Code is not released with this version. The paper provides full algorithmic pseudocode, all hyperparameters and configuration details sufficient to reimplement the method, and the contract used in the stress test is given verbatim; all benchmarks used are public.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?
Answer: [Yes]
Justification: Section 4 specifies benchmarks, target models and protocols; Algorithm 1 lists every hyperparameter (beam width W W W , diversity slots D D D , quality-gate ratio ϱ \varrho ϱ , proposals per candidate k k k , horizon, momentum window, patience); data splits and their roles are defined in Section 2 and per-experiment settings are in Section F.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The contract stress test and the momentum ablation report mean ± \pm ± s.d. over three paired seeds, with paired per-seed differences; the critique ablation reports 95% bootstrap CIs over the target models. Benchmark comparisons use baselines as published, which report no seed variance, so margins of at most 0.5 pp are reported as matches rather than wins. Single-run results are identified as such.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: All experiments use cloud-hosted LLM APIs rather than local GPU compute. Algorithm 1 determines the number of LLM calls per step, and Section F reports measured inference cost.
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?
Answer: [Yes]
Justification: The research uses publicly available benchmarks (SST-5, GPQA, ARC, BBH, GSM8K, AIME-2025, PUPA, HelpSteer2), does not involve human subjects, and does not raise dual-use concerns. The method optimizes prompts for reasoning and classification tasks and does not generate harmful content.
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper’s motivation is a safety benefit: contract sections such as safety clauses, tool schemas and output formats are made unreachable, so optimization cannot edit them away (§ 1 ). § 6 states the main risks: SPLICE optimizes the reward it is given, so a misspecified reward is the dominant failure mode, and a frozen clause keeps its text but not necessarily its effect (compliance falls from 96.5% to 66.8%), so frozen blocks still need a behavioral audit.
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?
Answer: [N/A]
Justification: The paper does not release pre-trained models, scraped datasets, or other high-risk assets. The contribution is an optimization algorithm that operates on existing LLM APIs. The optimized prompts are task-specific text strings without inherent misuse risk beyond what the underlying LLMs already present.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [No]
Justification: All datasets are properly cited: SST-5 [75 ] , GPQA [64 ] , GSM8K [14 ] , ARC [13 ] , BBH [76 ] , AIME-2025 [4 ] , PUPA [73 ] , HelpSteer2 [80 ] . All prior methods are cited where techniques are adapted, and the LLM APIs are accessed through their official providers. We use only the public releases of these datasets, under the terms they are distributed with, but the paper does not restate their licenses.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [N/A]
Justification: No new assets (code, datasets, or models) are released with this submission. The algorithmic contribution is fully described via pseudocode (Algorithms 1–3) and formal definitions in the main text and appendix.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [N/A]
Justification: The paper does not involve crowdsourcing or research with human subjects. All evaluations are automated using standard benchmark metrics.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [N/A]
Justification: The paper does not involve human subjects research. All experiments are conducted using automated evaluation of LLM outputs against benchmark datasets.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: LLMs are central to the SPLICE methodology and are fully described. The proposal agent generates improved prompt variants (Algorithm 1, step iv). The critique agent produces dual textual gradients (Algorithm 1, step ii). Multiple system models across capability tiers serve as the target models being optimized (§ 4 ). The paper explicitly describes the role of each LLM component.