Black-Box LLM Optimization¶

Sometimes the only thing you can interact with is a function score(x) → float — an LLM-as-judge, a closed classifier, a private API — and you need to find an input x that maximizes it. You cannot differentiate through it, cannot inspect its weights, and every call costs money or tokens. This is the black-box optimization regime, and it shows up whenever a task says "the judge is frozen, here is a query budget, maximize the score."

What This Is¶

Given a scorer S(x) that you can only query, not differentiate, find:

x*  =  argmax_x  S(x)     subject to   query_count <= B

The inputs x are usually text (prompts, answers, instructions), but the same pattern applies to images, programs, molecules, or any structured object. You do not assume anything about S beyond "you can call it and get a number."

The search algorithms you should know by name:

Random search. Sample candidates from a proposal distribution, score them, keep the best. The baseline everything else must beat.
Beam search. Maintain the top-k candidates. At each step, generate variants of each and keep the top-k overall. Greedy but much stronger than random when variants are meaningful edits.
Bandit search (UCB / Thompson). Treat each candidate family as an arm; explore arms whose confidence intervals could beat the current best; exploit once a family's mean is clearly ahead. Efficient when the scorer is noisy.
Evolutionary search / CMA-ES-style. Keep a population, mutate and crossover, select by score. Handles rugged landscapes where local edits do not monotonically help.
LLM-guided search. Use an LLM to propose candidates conditional on the current best and the score history. "Here are prompts I tried and their scores; suggest three better prompts." The LLM is both the operator (proposing moves) and often the scorer (judging them).

When You Use It¶

the scorer is frozen — a closed LLM judge, a production classifier, a sandboxed evaluator
gradients are unavailable (API-only, non-differentiable pipeline, discrete output)
query budget is finite and measurable — every call costs; you must spend them on informative candidates
the search space has structure a human or model can exploit (prompts, programs, molecules) — pure random search is fine for 10-dim continuous spaces, hopeless for prompt-level text

Do Not Use It When¶

you can just fine-tune — if you have weights and data, a few thousand steps of gradient descent beats thousands of black-box queries almost every time
the scorer is trivial — if you can reverse-engineer S by reading the prompt, skip the search
the task rewards consistency across many inputs, not a single optimum — optimizing one x* is the wrong frame; you need a policy, which is RL territory

The Search Loop¶

The skeleton is the same for every method — only the propose/select rules differ:

best_score, best_x = -inf, None
history = []
while queries_used < B:
    candidates = propose(history, current_best=best_x)   # method-specific
    scores = [S(x) for x in candidates]                  # costs len(candidates) queries
    history.extend(zip(candidates, scores))
    if max(scores) > best_score:
        best_score = max(scores)
        best_x = candidates[argmax(scores)]
    if stopping_criterion(history): break
return best_x

Three decisions dominate the efficiency of this loop: the propose function, the query allocation (exploration vs exploitation), and the stopping rule.

Beam Search Over Prompts¶

Concrete template that actually works well for LLM-judge maximization:

beam = [seed_prompt]                 # start with one candidate
beam_size = 4
edits_per_candidate = 3
rounds = 10

for round_i in range(rounds):
    proposals = []
    for p in beam:
        for _ in range(edits_per_candidate):
            proposals.append(mutate(p))     # LLM-suggested edit, synonym swap, reordering
    proposals += beam                       # keep the parents around
    scores = [judge(p) for p in proposals]  # batch if API allows
    ranked = sorted(zip(proposals, scores), key=lambda t: -t[1])
    beam = [p for p, _ in ranked[:beam_size]]

Total queries: rounds * (beam_size * edits_per_candidate + beam_size) ≈ rounds * beam_size * (edits + 1). Pick these so the product fits your budget.

Handling A Noisy Scorer¶

LLM judges are stochastic: the same x can get different scores on different calls. Two implications:

never trust a single score. For a candidate you want to commit to, query it n_reps times and use the mean (or a lower confidence bound if you are being conservative).
query budget trades off width vs depth. B total queries split as "width" (number of distinct candidates) × "depth" (reps per candidate). A common heuristic: depth = 3-5 once a candidate is in the top beam, depth = 1 for new proposals until they survive one round.

The UCB move explicitly manages this: prefer candidates with high mean + c * sqrt(log(total) / visits), which naturally pulls queries toward both high-mean and low-visit candidates.

Reward Shaping¶

When the raw score is 0/1 (pass/fail), optimization gets stuck — most proposals score 0, gradient of useful information is flat. Three shaping moves:

add a partial-credit signal. If the judge exposes sub-scores (correctness, format, length), combine them. Even a noisy continuous signal beats a binary one.
use a surrogate scorer. If the real scorer is expensive, train a cheap proxy on its outputs and use the proxy during exploration. Re-query the real scorer only to break ties and confirm.
penalize cost directly. Add -λ * length(x) or -λ * token_count so the search does not drift toward long, verbose candidates that happen to score well because they hedge.

What To Inspect¶

score-vs-queries curve. Plot best-so-far on y-axis, queries used on x. A good search has a steep early rise and a slowing plateau. A flat curve means your propose function is not producing useful edits.
scorer variance on a fixed candidate. Query the current best 20 times and plot the distribution. The standard deviation tells you how many reps you need for confident comparisons.
diversity of the beam. If all beam members are near-paraphrases, you are exploiting too early. Inject mutation strength or keep a "diverse" slot that ignores score for one round.
judge failure modes. Look at a few high-scoring candidates and confirm the judge is scoring what the task says it should. Reward hacking — the search finds a quirk of the judge, not a real solution — is the dominant failure mode.
compare to random-search baseline at equal budget. If your fancy method is not beating random search on the same query budget, something is wrong with your proposer or your budget is too small to matter.

Failure Pattern¶

reward hacking. The judge has a quirk (rewards long answers, rewards specific formatting, rewards confident tone regardless of correctness). The optimizer finds it and the best x* is gibberish that happens to trigger it. Fix: sanity-check with a second judge; or shape the reward to penalize the quirk.
exploration collapse. The beam narrows to one candidate family in round 2 and never escapes. Fix: keep a diverse slot, increase mutation strength, or restart with a different seed prompt.
budget blown on noise. You queried the same low-variance candidate 30 times to shrink its confidence interval, while 29 unexplored candidates sit untouched. Fix: UCB-style allocation, or cap reps per candidate.
surrogate-scorer drift. You trained a proxy, search against the proxy, then the real judge disagrees. Fix: periodically re-train the proxy on fresh real-judge samples from the current search region.
proposer that does not learn from history. Each round's proposals ignore previous scores. Fix: pass the top-k history into the LLM proposer so it knows what has already been tried and how it scored.

Quick Checks¶

are you tracking queries used vs budget? (a bar chart of budget remaining is worth having)
have you computed the scorer's variance on a fixed candidate? (tells you how many reps are required)
is there a random-search baseline on the same budget that your method beats?
does your proposer condition on prior scores, or is it stateless?
is your stopping criterion tied to improvement, not just total queries? (stop early if best-so-far has not moved in N rounds)

Practice¶

Run academy/labs/black-box-llm-search/src/search_workflow.py:

sets up a stochastic synthetic scorer with a known but non-trivial optimum (e.g., target phrase buried in a scoring rubric)
compares four search strategies at equal query budget: random search, beam search with random mutations, beam search with LLM-proposed mutations (simulated by a rule-based proposer), and UCB-style bandit search
reports best-score-vs-queries curves and the query spend per method
adds a reward-hacking demo: introduce a "length bonus" to the scorer and watch the methods diverge toward verbose nonsense unless you add a length penalty

You should leave able to explain when black-box search is the right move, how to split a query budget between exploration and verification, and why reward hacking is the first failure mode to check for.

Longer Connection¶

Black-box input optimization is one of the big recurring patterns in modern ML contests. Related instances:

prompt engineering by search — search the prompt string against an LLM judge
textual inversion and activation steering — continuous-space version, differentiable (see Steering Frozen Generative Models)
AutoML and hyperparameter search — the "scorer" is model validation performance
molecular design against a docking score — the scorer is a physics simulator
adversarial attack generation against a closed classifier — the scorer is "did I flip the prediction?"

The common structure — frozen scorer, bounded query budget, search over a structured input space — is why the same toolkit (beam search, UCB, evolutionary search, LLM-guided proposals) solves all of them with minor changes. Recognizing that a task is "black-box optimization" is usually half the work.