SPLICE: Structured Prompt Local Iterative Combinatorial Evolution
Conference on Neural Information Processing Systems (NeurIPS), 2026
Treats a production prompt as a set of blocks, some frozen and some editable, and optimizes it with section-local textual gradients and elitist beam search, giving the first formal guarantees for iterative LLM-driven prompt optimization. Outperforms prior prompt optimizers across benchmarks and three model capability tiers while keeping frozen sections verbatim.
Abstract
Production LLM agents are multi-section artifacts spanning thousands of tokens, where some sections encode hard-won contracts (safety clauses, tool schemas, output formats) that must not drift, and others are legitimate optimization targets. Existing iterative prompt optimizers treat the prompt as a monolithic string, producing three recurrent failure modes: unsafe global rewrites, beam collapse onto a single lineage, and unchecked prompt bloat; none addressed by formal guarantees. This work proposes SPLICE, that frames iterative prompt optimization as combinatorial search over an edit graph of block-structured, selectively-mutable prompt states, under which a broad class of existing methods reduces to selector–proposal instances of a single batched iterative prompt search template. Within this framework we map each failure mode to a matched guarantee: (i) per-block mutability preserves contracts verbatim, with a price-of-freezing bound showing the trade-off is nearly free when frozen blocks carry small marginal gains; (ii) elitist beam search with lineage-aware diversity slots gives deterministic monotonicity, exponential no-regression tails, and conditional no-collapse, without requiring a temperature parameter; (iii) a scale-invariant ratio regularizer on prompt growth yields an explicit accuracy–length bias bound. These selectors are driven by dual section-local textual gradients, for which an edit-graph reachability result bounds the probability that an improving child arrives at a given step. We give a theoretical account of the search dynamics of iterative LLM-driven prompt optimization in which every guarantee’s assumptions are stated and its empirical check named. Empirically, across seven benchmark tasks spanning classification to LLM-as-judge alignment and a wide range of foundation models, SPLICE matches or exceeds the strongest prior method on six of seven while preserving frozen sections verbatim. Component ablations attribute the gains axis by axis, and we report the two axes that carry no measurable weight alongside those that do.