A Hybrid Nested Harness for Decoupling Structure and Parameters in LLM-Driven Optimization

AI summary

Overview

Research area: Machine learning — LLM-driven program/algorithm discovery, evolutionary search, and bilevel (nested) optimization.

Technical level: Intermediate to Advanced. The paper assumes familiarity with evolutionary search loops, black-box optimizers such as CMA-ES, and Bayesian inference tooling (VI, NUTS, SBC), though its central idea — splitting structure from numbers — is explained plainly.

Scope in one sentence: The paper proposes and empirically validates a "hybrid nested harness" in which a frozen LLM proposes program structure with numeric gaps and a pluggable numerical solver fills those gaps, across meta-optimization, executable policies, and approximate Bayesian inference.

What This Paper Is About

Systems that put a frozen LLM in an evolutionary loop typically ask the model to propose an entire artifact — a policy function, a training script, a probabilistic-model reparameterization — in a single text turn, which forces the same operator to update both control-flow structure and continuous numeric constants like learning rates or thresholds. Language models are comparatively good at the first and weak at the second, so they waste tokens taking discrete jumps through a trial-and-error loop over numbers a dedicated solver could handle directly. The goal of this paper is to formalize that split as a bilevel nested search, where an outer text-based optimizer searches structure and an inner numerical optimizer tunes the parameters embedded in it, and to show empirically that this factorization beats both vanilla LLM-driven joint search and pure numerical optimization.

Key Contributions

1. Formalization of hybrid nested search as a bilevel objective. A candidate program is written as a pair ⟨τ, θ⟩, where τ is a structure drawn from a discrete sketch space with h(τ) numeric "holes" and θ ∈ Θ(τ) ⊆ ℝ^{h(τ)} is the parameter vector. The structural value F(τ) = max_{θ ∈ Θ(τ)} f(τ, θ) is what the outer LLM search is scored against, and Algorithm 1 gives a (1+1) outer loop with a pluggable inner Tune routine.

2. Identification and analysis of "parametric aliasing." The paper names the failure mode in which a pure text-based search ranks structures by the LLM's untuned guess g_van(τ) = f(τ, θ̄(τ)) rather than the parametric optimum, and defines the parameter-tuning gap Δ(τ) = F(τ) − f(τ, θ̄(τ)) ≥ 0. Proposition 1 shows the inner loop de-aliases the outer ranking, with proof in Appendix A, yielding the falsifiable prediction that hybrid advantage is proportional to E_{τ~M}[Δ(τ)].

3. A pluggable interface — the "manifest." Instead of parsing numeric literals out of generated code, the LLM emits, for each gap j, a tuple (j, ℓ_j, u_j, type_j, θ̄_j) with lower bound, upper bound, a type from {cont, int, log, pow2}, and its own suggested value θ̄_j used as a warm start.

4. Validation across three scientific domains and multiple solver/model combinations. Meta-optimizers, code-based policies for systems research and social dilemmas, and approximate Bayesian inference — with inner solvers CMA-ES, VI, and NUTS, outer optimizers including a (1+1) LLM loop and reflective prompt evolution (GEPA), and several proposer model families. Code is released at github.com/vicgalle/hybrid-nested-search.

Main Findings

• Hybrid search beats both baselines across all three domains. In every problem family, the hybrid optimizer is reported as superior to vanilla LLM-driven search and to pure numerical optimization baselines.

• Meta-optimizers: gains up to twelve orders of magnitude. On hidden 2-D objectives with a (1+1) LLM outer loop and CMA-ES inner, hybrid moves delivered loss by up to twelve orders of magnitude on ackley and rosenbrock. Representative values with GLM-5.2: rosenbrock vanilla 2.1×10⁻⁴, numerical 4.2×10⁻¹³, hybrid 1.5×10⁻¹²; rastrigin vanilla 19.2, numerical 9.95, hybrid 1.22; ackley vanilla 13.1, numerical 4.4×10⁻¹², hybrid 3.3×10⁻⁹; schwefel vanilla 405, numerical 358, hybrid 297. On ellipsoid the two search strategies tie (vanilla 2.3×10⁻⁴⁰, numerical 8.6×10⁻¹⁴, hybrid 3.0×10⁻²⁸).

• The aliasing trap is the mechanism. A momentum or adaptive optimizer at default parameters overshoots and diverges, so the LLM's untuned guess scores ∞ or plateaus and pure text-based search discards a good structure. Hybrid hands the structure to CMA-ES, which finds a stable configuration; hybrid also beats the oracle direct-CMA-ES on the multimodal rastrigin and ackley cases, typically with much less function evaluations.

• Cloud-systems policies: hybrid wins every regime evaluated. For Can't Be Late · costly with Gemini 3.5 Flash, cost was vanilla 126.9, numerical 124.4, hybrid 120.5 (advantage 5.0%). For Cloudcast · inter, vanilla 213.3, numerical 317.4, hybrid 168.7 — a 20.9% advantage, or 1.9× over pure CMA-ES tuning a hand-designed topology.

• Cleanup social dilemma: 9/9 model × seed runs. Hybrid achieves the highest utilitarian welfare U in all nine runs, and its advantage over pure CMA-ES grows monotonically with difficulty. All three models independently converge on the same algorithmic family (deadzone + ramp + saturation cap) optimized to the same welfare on heavy (0.582 for all three). On heavy with Gemini, a piecewise ramp policy is the worst untuned proposal (U = −0.10) yet the best tuned one (U = 0.582); vanilla search discards it, promotes a sigmoid policy, and peaks at U = 0.480, leaving approximately 21% to aliasing.

• The factorization is orthogonal to the outer optimizer. Replacing the loop of Algorithm 1 with GEPA while keeping CMA-ES inner, hybrid beats tuner-free GEPA in every regime with a non-negligible Δ (6/8 regimes; the two lowest-gap regimes tie). The marginal value of the inner loop shrinks from approximately 10–20% with the (1+1) evolutionary loop to approximately 5–10% with GEPA.

• Bayesian inference: a VI-vs-NUTS asymmetry the theory predicts. NUTS warmup already adapts a linear preconditioner, so affine reparameterizations are redundant under NUTS (Δ ≈ 0) but valuable under VI. Under VI the affine Gaussians win (+37.7 / +9.3 nats) yet tie under NUTS; under NUTS the nonlinear funnel and eight-schools win (+3.1 / +2.2 decades) yet the affine controls tie. Representative values: gauss_rot (VI) vanilla −33.4, hybrid 4.30, advantage +37.7 nats; funnel (NUTS) numerical 8.4×10⁻⁵, hybrid 0.111, +3.12 dec; eight_schools (NUTS) numerical 3.8×10⁻⁴, hybrid 0.056, +2.17 dec; horseshoe (D=18, NUTS, Gemini 3.1 Pro) numerical 6.2×10⁻⁴, hybrid 1.48×10⁻², +1.37 dec.

• Reference-free certification with SBC. On a sticky horseshoe logistic regression (D = 18) where identity-plus-adaptation suffers 520 divergences (ESS/grad 6.2×10⁻⁴), every one of five proposer models found an SBC-certified reparameterization giving ≥ 10× ESS/grad (up to 24×), with 0/25 live proposals SBC-rejected. SBC also rejects a constructed trap, θ = C tanh(z) — a smooth non-singular bijection that samples easily but targets a truncated, wrong posterior — which ESS, R̂, and the Jacobian smoke-test all green-light.

• The cleanest de-aliasing result: banana (D = 10). All three proposer models constructed the required nonlinear quadratic shear b ← b − c·a² given only the generative structure, with curvature c a single hidden nonlinear hole. Vanilla proposes the same shear at a guessed curvature (ELBO ≈ −74); hybrid tunes the one hidden constant to ELBO −13, a +60-nat win from tuning a single parameter on an identical structure. Once VI finds c, NUTS samples the de-curved space at +1.57 decades (≈37×), a NeuTra-style pipeline where the two inner solvers compose.

• Cost overhead is argued to be modest. Hybrid cost is C_hyb = K(c_llm + B_in·c_ev) versus C_van = K·c_llm, a factor (1 + c_ev/c_llm·B_in) more. With c_ev/c_llm ~ 10⁻²–10⁻³ and B_in ~ 100, this adds only 10–100% overhead. The comparison inverts in expensive-evaluation domains such as full training runs, where CMA-ES is the wrong inner solver.

• No universal dominance claimed. The paper invokes the No Free Lunch theorem and predicts hybrid search merely ties when the problem is not near decomposable, carries no structural prior, has a negligible parametric gap, or is expensive to evaluate — matching observed ties on ellipsoid, intra-cloud routing, and the deceptive schwefel.

Methodology in Plain English

The researchers split every candidate solution into two parts. The structure is the program topology — branches, hard logic, auxiliary function definitions — expressed as text and left to the LLM, which has a useful knowledge prior over code. The parameters are the numeric values embedded in that structure — thresholds, learning rates, scales — treated as a continuous (possibly mixed-integer) black-box optimization problem and handed to a numerical solver.

To connect the two, the LLM does not just write code. It writes a sketch with explicit numeric holes plus a manifest describing each hole: its lower bound, upper bound, type (continuous, integer, log-scaled, or power-of-2), and its own best guess. The numerical Tune routine takes that guess as a warm start, searches within the declared bounds, projects integer and power-of-2 coordinates onto their feasible lattice, and returns both the best parameters and an estimate F̂(τ) of the structure's optimized fitness.

The outer loop is simple: the LLM proposes a new structure conditioned on textual feedback — the previous structure, its tuned value F̂(τ_{k−1}), its optimized parameters, and domain diagnostics such as compiler errors. A Validate check rejects malformed sketches, and a structure is promoted only if its tuned value beats the incumbent. This promotion-on-tuned-value rule is the core fix: the LLM is told the structure's potential at its parametric best rather than the score of its own numeric guess.

Two design safeguards against overfitting are described. The fitness function is an aggregate (for example, a mean across several samples) so it cannot trade robustness for a single lucky point, and a held-out evaluation function is run once on the tuned incumbent at a sample never folded into feedback. In the Bayesian domain, that held-out gate is a longer multi-chain run scoring divergences, R̂, and effective sample size, or simulation-based calibration for a reference-free correctness check.

Throughout the experiments, the objective function is withheld from the LLM: prompts show only the artifact interface and a structural description, so the measured Δ gap is the model's genuine miscalculation rather than a value it could have read off. The default inner budget is B_in = 100 unless noted, and three strategies are compared: vanilla autoresearch (LLM joint search, no inner loop), pure numerical (inner solver over a fixed structure, no structural search), and hybrid.

Why This Matters

Impact on research. The paper reframes a common assumption in LLM-based discovery systems — that the model should emit the whole artifact in one turn — as a variable-type assignment problem. It supplies a theory of when the split helps (parametric aliasing, Proposition 1) and a falsifiable prediction that advantage tracks E[Δ], which makes the claim testable rather than anecdotal. It also shows the inner tuner composes with existing text-based optimizers such as GEPA instead of competing with them, and that the same factorization applies when the inner solver is a sampler or variational inference rather than CMA-ES.

Real-world applications.

• Cloud scheduling: the Can't Be Late spot/on-demand scheduler, where the LLM proposes how state (remaining work, slack to deadline, restart overhead) maps to actions and the tuner adjusts slack buffers and pressure thresholds to minimize dollars under a hard deadline.

• Multi-cloud routing: the Cloudcast broadcast router, where the LLM proposes routing topology (shared relay trees, hub routing, k-shortest multipath) and the tuner adjusts parameters such as weights and tolerances.

• Multi-agent resource management: the Cleanup public-goods gridworld, a sequential social dilemma trading individual apple collection against collective river cleaning, where the LLM writes role-assignment policies and welfare is evaluated by self-play.

• Probabilistic modeling and inference tooling: LLM-authored reparameterizations that make hard posteriors (funnel, eight-schools, sticky horseshoe, curved-ridge banana) sampleable, certified by simulation-based calibration before use.

Industry relevance. The cost argument matters for practitioners paying for high-thinking-budget LLM calls: if each expensive proposal is exhausted by a cheap inner solver costing 10⁻²–10⁻³ per evaluation, hybrid search adds only 10–100% overhead at B_in ~ 100 while extracting far more from each proposal. The paper positions the method as a human-in-the-loop copilot rather than an autonomous frontier system, which fits industrial workflows where a domain expert defines the sketch interface and manifest bounds.

Future Directions

• A neural inner operator for high-dimensional holes. The generalist CMA-ES degrades past a few dozen dimensions, so h(τ) must currently be capped; the paper explicitly leaves high-dimensional holes to further work.

• Sample-efficient inner solvers for expensive-evaluation domains. The cost analysis inverts when each evaluation is a full training run; substituting a sample-efficient optimizer, or amortizing tuning across structures, is named as the needed change while the factorization is claimed to still hold.

• Specialized solvers for mixed-integer holes. The limitations section notes that mixed-integer holes need more specialized solvers than the generalist approach used here.

• Robust manifest parsing and the novelty ceiling. The manifest must be parseable for the method

Authors’ abstract

In evolutionary algorithms powered by language models, the LLM acts as a single operator that simultaneously updates structural components (like control flow) and continuous parameters. While LLMs can be good at the first, they are not efficient at the second, wasting tokens taking discrete jumps inside a trial and error loop. We resolve this by formalizing a hybrid nested search, in which an outer loop has the LLM propose a structural sketch, with numeric gaps, and an inner numerical optimizer tunes the sketch. Both the outer and inner solvers are pluggable: any text-based optimizer can be combined with a zero-order optimizer (CMA-ES), gradient-based routines, or MCMC samplers. We validate our framework across three scientific domains: (i) meta-optimizers on closed-form test functions, (ii) code-based policies for systems research and social dilemmas; and (iii) approximate Bayesian inference tasks. Across all three, the hybrid optimizer is superior to both vanilla LLM-driven search and pure numerical optimization baselines. Code at: https://github.com/vicgalle/hybrid-nested-search